text:
# 1 Introduction

## 1 Introduction

The neutral $`B`$ meson decay modes $`BD_{}^{}{}_{}{}^{+}h^{}`$, where $`h^{}`$ is a light hadron ($`\pi ^{},\rho ^{},a_1^{}`$), have been proposed  for use in theoretically clean measurements of the Cabibbo-Kobayashi-Maskawa  unitarity triangle parameter $`\mathrm{sin}(2\beta +\gamma )`$. Since the time-dependent CP asymmetries in these modes are expected to be of order 2%, large data samples and multiple decay channels are required for a statistically significant measurement. The low efficiency of reconstructing the $`D^0`$ produced in the $`D^{}`$ decay leads to significant loss of signal events. Partial reconstruction of the $`B`$ meson results in substantially larger efficiency, albeit with higher backgrounds. The overall $`\mathrm{sin}(2\beta +\gamma )`$ sensitivity is expected to be roughly similar for partial and full reconstruction, and about 90% of the partially reconstructed events cannot be fully reconstructed. Therefore, both full and partial reconstruction can and should be used for the $`\mathrm{sin}(2\beta +\gamma )`$ measurement.

The measurement of the $`B^0`$ lifetime, presented here, constitutes a first step toward measuring $`\mathrm{sin}(2\beta +\gamma )`$ with partial reconstruction of $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$. In this analysis, we have developed the procedures for candidate reconstruction, background characterization, vertexing, and fitting, all critical components of the time-dependent $`\mathrm{sin}(2\beta +\gamma )`$ analysis.

## 2 The BABAR Detector and Data Sample

The data used in this analysis were collected with the BABAR detector at the PEP-II storage ring. The data consist of 22.7 million $`B\overline{B}`$ pairs, corresponding to an integrated luminosity of 20.7 $`\text{ fb}^1`$ recorded at the $`\mathrm{{\rm Y}}(4S)`$ resonance. In addition, 2.6 $`\text{ fb}^1`$ were collected about 40 MeV below the resonance. This off-resonance sample is used to study the continuum, $`e^+e^{}q\overline{q}`$ background, where $`q=\{u,d,s,c\}`$.

The BABAR detector, described in detail elsewhere , consists of five sub-detectors. Surrounding the beam-pipe is a five-layer silicon vertex tracker (SVT), providing precision measurements of the positions of charged particles close to the interaction point and tracking of charged particles with low transverse momentum. Outside the support tube that surrounds the SVT is a 40-layer drift chamber (DCH), filled with an 80:20 helium-isobutane gas mixture. The DCH provides charged particle momentum measurements in a 1.5 T magnetic field, and ionization energy loss measurements that contribute to charged particle identification. Surrounding the DCH is a detector of internally reflected Cherenkov light (DIRC), providing charged particle identification. Outside the DIRC is a CsI(Tl) electromagnetic calorimeter (EMC), used mainly to detect and measure the energy of photons and to provide electron identification. The EMC is surrounded by a superconducting coil, which generates the magnetic field for tracking. Outside the coil, the flux return iron is instrumented with resistive plate chambers, used mainly for muon identification.

PEP-II is an asymmetric energy storage ring, with positron and electron beam energies of about 3.11 and 9.0 GeV. The center-of-mass (CM) frame of the average $`e^+e^{}`$ collision is therefore boosted along the $`z`$ direction in the lab frame, enabling time-dependent measurements involving reconstruction of $`B`$ mesons.

## 3 Analysis Method

### 3.1 Partial Reconstruction

To partially reconstruct a $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$ candidate555Charge conjugate decays are also implied. , only the $`\rho `$ and the $`\pi _s`$, the soft pion from the decay $`D_{}^{}{}_{}{}^{+}D^0\pi _s^+`$ decay, are reconstructed. The angle between the momenta of the $`B`$ and the $`\rho `$ in the CM frame is then computed:

$$\mathrm{cos}\theta _{B\rho }=\frac{M_{D_{}^{}{}_{}{}^{+}}^2M_{B^0}^2M_\rho ^2+E_{\mathrm{CM}}E_\rho }{2P_B|\stackrel{}{p}_\rho |},$$
(1)
where $`M_x`$ is the mass of particle $`x`$, $`E_\rho `$ and $`\stackrel{}{p}_\rho `$ are the measured CM energy and momentum of the $`\rho `$, $`E_{\mathrm{CM}}`$ is the total CM energy of the beams, and $`P_B=\sqrt{E_{\mathrm{CM}}^2/4M_{B^0}^2}`$. Given $`\mathrm{cos}\theta _{B\rho }`$ and the measured four-momenta of the $`\pi _s`$ and the $`\rho `$, the $`B`$ four-momentum may be calculated up to an unknown azimuthal angle $`\varphi `$ around $`\stackrel{}{p}_\rho `$. For every a value of $`\varphi `$, the expected $`D`$ four-momentum, $`𝒫_D(\varphi )`$, is determined from four-momentum conservation, and the $`\varphi `$-dependent “missing mass” is calculated, $`m(\varphi )\sqrt{|𝒫_D(\varphi )|^2}`$. With $`m_{\mathrm{max}}`$ and $`m_{\mathrm{min}}`$ being the maximum and minimum values of $`m(\varphi )`$ obtained by varying $`\varphi `$, we define the missing mass, $`m_{\mathrm{miss}}\frac{1}{2}\left[m_{\mathrm{max}}+m_{\mathrm{min}}\right]`$. This variable peaks around $`M_{D^0}`$, the nominal $`D^0`$ mass, for signal events, with a spread of about 3.5 MeV, while background events are more broadly distributed.

We define the $`D^{}`$ helicity angle $`\theta _D^{}`$ to be the angle between the directions of the $`D`$ and the $`B`$ in the $`D^{}`$ rest frame. The value of $`\mathrm{cos}\theta _D^{}`$ is computed as in Ref. . The $`\rho `$ helicity angle $`\theta _\rho `$ is defined as the angle between the directions of the $`\pi ^0`$ (from the decay of the $`\rho `$) and the CM frame in the $`\rho `$ rest frame. Since the $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$ decay is $`(87.8\pm 4.5)\%`$ longitudinally polarized , the $`\mathrm{cos}\theta _\rho `$ and $`\mathrm{cos}\theta _D^{}`$ distributions of signal events peak toward $`\pm 1`$. Background events have fairly flat distributions, with $`B\overline{B}`$ background increasing in the region of soft $`\pi _s`$ and $`\pi ^0`$, making $`\mathrm{cos}\theta _D^{}`$ and $`\mathrm{cos}\theta _\rho `$ useful for background suppression. With knowledge of $`\mathrm{cos}\theta _D^{}`$ and $`\mathrm{cos}\theta _{B\rho }`$, the 3-momentum of the $`D`$ is determined, up to a two-fold ambiguity and detector resolution effects.

### 3.2 Event Selection

In order to suppress the continuum background, we select events in which the ratio of the 2nd to the 0th Fox-Wolfram coefficients  is smaller than 0.35. Charged $`\rho `$ candidates are identified by their decay to a “hard” charged pion, $`\pi _h`$, and a $`\pi ^0`$. To suppress fake $`\pi ^0`$ candidates, the $`\pi ^0`$ momentum in the CM frame is required to be greater than 400 MeV. The invariant mass of the $`\pi ^0`$ candidate must be within 20 MeV of the nominal $`\pi ^0`$ mass. Both the $`\pi _h`$ and $`\pi _s`$ candidate tracks are required to originate within 1.5 cm of the interaction point in the $`xy`$ plane (the plane perpendicular to the beam) and within $`\pm 10`$ cm of the interaction point along the direction of the beams. Tracks are rejected if their specific ionization and/or Cherenkov angle indicate that they are highly likely to be a kaon or a lepton. The invariant mass $`m(\rho )`$ of the $`\rho `$ candidate must be between 0.45 and 1.1 GeV.

The computed cosine of the angle between the $`B`$ and $`\rho `$ must satisfy $`|\mathrm{cos}\theta _{B\rho }|1`$. To suppress combinatoric background, we require $`|\mathrm{cos}\theta _\rho |>0.3`$ and $`|\mathrm{cos}\theta _D^{}|>0.3`$, and reject events in the range $`\mathrm{cos}\theta _\rho >0.3`$ and $`\mathrm{cos}\theta _D^{}<0.3`$.

For each $`\rho ^\pm \pi _s^{}`$ pair that satisfies the above requirements, $`m_{\mathrm{miss}}`$ is calculated. The pair with the smallest value of $`|m_{\mathrm{miss}}M_{D^0}|`$ in the event is selected, and all others are discarded. Similarly, the “wrong-sign” $`\rho ^\pm \pi _s^\pm `$ pair with the smallest $`|m_{\mathrm{miss}}M_{D^0}|`$ is retained for background studies, as described below. Right-sign events in the range $`1.810<m_{\mathrm{miss}}<1.840`$ GeV are classified as sideband events, and are used for background studies. Right- and wrong-sign events satisfying $`m_{\mathrm{miss}}>1.845`$ GeV are classified as signal region events. All other events are discarded. The efficiency of signal events to satisfy all the signal region criteria is 6.4%.

Events that could be fully reconstructed in the $`D^0`$ decay modes $`D^0K^{}\pi ^+`$ or $`K^{}\pi ^+\pi ^0`$ are tagged as fully reconstructed. In addition to satisfying the partial reconstruction criteria above, fully reconstructed events are identified by requiring that the reconstructed $`D`$ invariant mass be within 40 MeV of $`M_{D^0}`$, the difference between the $`D^{}`$ and $`D`$ invariant masses be between 142 and 150 MeV, the reconstructed CM $`B`$ energy be within 50 MeV of $`E_{\mathrm{CM}}/2`$, and $`m_{\mathrm{ES}}>5.25`$ GeV, where $`m_{\mathrm{ES}}\sqrt{E_{\mathrm{CM}}^2/4p_B^2}`$ is the beam energy substituted mass and $`p_B`$ is the reconstructed CM momentum of the $`B`$ meson.

### 3.3 Measurement of the Decay Time Difference

The decay position $`z_{\mathrm{rec}}`$ of the partially reconstructed $`B`$ candidate along the beam direction is determined by constraining the $`\pi _h`$ track to originate from the beam-spot in the $`xy`$ plane. To account for the $`B`$ meson flight in the $`xy`$ plane, $`30\mu \mathrm{m}`$ are added in quadrature to the beam-spot size. The $`\pi _s`$ is not used in this vertex fit in order to simplify the classification of the background, and since its contribution to the vertex precision is small, due to multiple scattering.

The decay position $`z_{\mathrm{other}}`$ of the other $`B`$ meson along the beam direction, is obtained with all tracks excluding the $`\pi _h`$, the $`\pi _s`$, and any track whose CM angle with respect to either of the two calculated directions of the $`D`$ is smaller than 1 radian. This “cone cut” reduces $`N_{\mathrm{tr}}^D`$, the number of $`D`$ daughter tracks used in the other $`B`$ vertex. The remaining tracks are fit with a constraint to the beam-spot in the $`xy`$ plane. The track with the largest contribution to the $`\chi ^2`$ of the vertex, if greater than 6, is removed from the vertex, and the fit is carried out again, until no track fails this requirement.

The decay time difference $`\mathrm{\Delta }t=(z_{\mathrm{rec}}z_{\mathrm{other}})/\gamma \beta c`$ is then calculated, where $`\gamma \beta `$ is the CM frame boost. The value of $`\gamma \beta `$ is continuously determined from the beam energies, and averages 0.55. The estimated error $`\sigma _{_{\mathrm{\Delta }t}}`$ in the measurement of $`\mathrm{\Delta }t`$ is calculated from the parameters of the tracks used in the two vertex fits.

Events are rejected if the $`\chi ^2`$ probability of the $`\pi _h`$ vertex fit is smaller than 1%, or if the $`\chi ^2`$ probability of the other $`B`$ vertex is smaller than 0.5%. We also require $`|\mathrm{\Delta }t|<15`$ ps and $`0.3<\sigma _{_{\mathrm{\Delta }t}}<4`$ ps.

The quantities $`z_{\mathrm{rec}}`$ and $`z_{\mathrm{other}}`$ are computed in the same way for fully reconstructed candidates as they are for partially reconstructed candidates. Using the Monte Carlo simulation, it is verified that with the 1 radian cone cut, the $`N_{\mathrm{tr}}^D`$ distribution of events that are fully reconstructed in the mode $`D^0K^{}\pi ^+`$ or $`K^{}\pi ^+\pi ^0`$ is in good agreement with the distribution of partially reconstructed events.

### 3.4 Backgrounds

The types of events in the partially reconstructed on-resonance sample are classified as follows:

1. Signal: $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$ events, in which the $`\pi _h`$ is correctly identified. This requirement ensures that $`z_{\mathrm{rec}}`$ is the decay position of the $`B`$ meson, up to the effect of detector resolution. The $`\pi _s`$ or the $`\pi ^0`$ candidates may be mis-reconstructed.
2. $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$: $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ events, in which the $`\pi _h`$ is a daughter of the $`a_1`$, and hence originates from the decay point of the $`B`$ meson.
3. Peaking $`B^0\overline{B}^0`$ background: $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$ and some $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ events, in which the $`\pi _h`$ originates from the other $`B`$ meson, resulting in the measurement $`\mathrm{\Delta }t=0`$, up to the effect of detector resolution and the selection of tracks used in the other $`B`$ vertex. The $`m_{\mathrm{miss}}`$ distribution of these events peaks around $`M_{D^0}`$, similar to signal events.
4. “Combinatoric” $`B\overline{B}`$ background: Random combinations of $`\pi _h`$, $`\pi ^0`$, and $`\pi _s`$ candidates, possibly including true $`\rho `$ decays.
5. $`\overline{B}D^{}\rho ^{}`$, where $`D^{}`$ stands for a charged or neutral resonance with mass in the range $`2.42.5`$ GeV decaying into $`D_{}^{}{}_{}{}^{+}\pi `$.
6. Continuum, $`e^+e^{}q\overline{q}`$ events.

### 3.5 Probability Density Function

An unbinned maximum likelihood fit is used to obtain the $`B^0`$ lifetime $`\tau _{_{B^0}}`$ from the data. The fit is performed simultaneously to on- and off-resonance data, and to on-resonance events which were fully reconstructed. The probability density function (PDF) is a function of $`\mathrm{\Delta }t`$, $`\sigma _{_{\mathrm{\Delta }t}}`$, and four “kinematic” variables: 1) $`m_{\mathrm{miss}}`$; 2) $`m(\rho )`$; 3) $`m_{\mathrm{ES}}`$; and 4) $`F`$, a Fisher discriminant that helps distinguish between $`B\overline{B}`$ and $`q\overline{q}`$ events. The value of $`F`$ is computed from the total CM energy flow of tracks and neutral EMC clusters (excluding the $`\rho `$ and the $`\pi _s`$) into nine volumes, defined by nine $`10^{}`$-wide concentric cones centered around the $`\rho `$ CM momentum $`\stackrel{}{p}_h`$. Each cone is folded to combine the energy flow in both hemispheres with respect to $`\stackrel{}{p}_h`$.

The PDF of partially reconstructed on-resonance events is a sum of terms corresponding to the different event types:

$`𝒫(\stackrel{}{\xi })`$ $`=`$ $`f_{\mathrm{signal}}𝒫_{\mathrm{signal}}(\stackrel{}{\xi })+f_{D^{}a_1}𝒫_{D^{}a_1}(\stackrel{}{\xi })`$ (2)
$`+`$ $`f_{\mathrm{peak}B^0}𝒫_{\mathrm{peak}B^0}(\stackrel{}{\xi })+f_{B\overline{B}}𝒫_{B\overline{B}}(\stackrel{}{\xi })`$
$`+`$ $`f_D^{}𝒫_D^{}(\stackrel{}{\xi })+f_{q\overline{q}}𝒫_{q\overline{q}}(\stackrel{}{\xi }),`$
where $`\stackrel{}{\xi }(m_{\mathrm{miss}},m(\rho ),F,\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ is the vector of fit variables,

$$𝒫_i(\stackrel{}{\xi })_i(m_{\mathrm{miss}})_i(m(\rho ))_i(F)𝒯_i(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})$$
(3)
is the PDF corresponding to event type $`i`$, and $`f_i`$ is the fraction of events of type $`i`$ in the data sample, where $`_if_i=1`$.

The PDF of the off-resonance sample is $`𝒫_{q\overline{q}}`$, which is also used to describe the continuum component of the on-resonance events in Eq. (2).

The PDF of fully reconstructed events is similar to $`𝒫(\stackrel{}{\xi })`$, except that $`_i(F)`$ is replaced by the function $`(m_{\mathrm{ES}})`$. The fractions $`f_{D^{}a_1}^\mathrm{f}`$, $`f_{\mathrm{peak}B^0}^\mathrm{f}`$, and $`f_{B\overline{B}}^\mathrm{f}`$ for this sample are determined from the Monte Carlo simulation, and are of order a few percent. The fractions $`f_{\mathrm{signal}}^\mathrm{f}`$ and $`f_{q\overline{q}}^\mathrm{f}`$ are obtained from a 3-dimensional fit to the $`m_{\mathrm{miss}}`$, $`m(\rho )`$, and $`m_{\mathrm{ES}}`$ distributions of this sample.

The $`m_{\mathrm{miss}}`$ distribution of signal events is parameterized as a bifurcated Gaussian,

$$_{\mathrm{signal}}(m_{\mathrm{miss}})\mathrm{exp}\left(\frac{(m_{\mathrm{miss}}M)^2}{2\sigma ^2}\right),$$
(4)
where $`M`$ is the position of the peak, and the value of $`\sigma `$ depends on the sign of $`m_{\mathrm{miss}}M`$. The proportionality constant in this and subsequent PDF expressions is determined by integrating the PDF over the allowed range of the PDF variable. The $`m_{\mathrm{miss}}`$ distributions of the background event types are parameterized as a bifurcated Gaussian plus an ARGUS function ,

$`A(m_{\mathrm{miss}})`$ $``$ $`m_{\mathrm{miss}}\sqrt{1\left(m_{\mathrm{miss}}/M_A\right)^2}`$ (5)
$`\times `$ $`\mathrm{exp}\left[ϵ\left(1\left(m_{\mathrm{miss}}/M_A\right)^2\right)\right],`$
where $`A(m_{\mathrm{miss}})=0`$ for $`m_{\mathrm{miss}}>M_A`$, and $`M_A`$ and $`ϵ`$ are parameters whose values are determined from fits to data or Monte Carlo simulation, as described in Sec. 3.6.

The $`_i(m(\rho ))`$ functions are sums of a relativistic P-wave Breit Wigner function and second-order polynomials. The functions $`_i(F)`$ are bifurcated Gaussians, and $`_i(m_{\mathrm{ES}})`$ are a Gaussian for signal events and ARGUS functions for the backgrounds.

The $`\mathrm{\Delta }t`$ PDF of signal events is an exponential decay with the $`B^0`$ lifetime, convoluted with a triple-Gaussian resolution function to account for finite detector resolution:

$`𝒯_{\mathrm{signal}}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ $`=`$ $`{\displaystyle \frac{1}{2\tau _{_{B^0}}}}{\displaystyle }d\mathrm{\Delta }t_te^{|\mathrm{\Delta }t_t|/\tau _{_{B^0}}}\times [f_nG_n(t_r,\sigma _{_{\mathrm{\Delta }t}})`$ (6)
$`+`$ $`f_wG_w(t_r,\sigma _{_{\mathrm{\Delta }t}})+f_oG_o(t_r,\sigma _{_{\mathrm{\Delta }t}})],`$
where $`\mathrm{\Delta }t_t`$ is the true decay time difference between the two $`B`$ mesons, $`t_r\mathrm{\Delta }t\mathrm{\Delta }t_t`$ is the $`\mathrm{\Delta }t`$ residual, $`G_n`$, $`G_w`$, and $`G_o`$ are the “narrow”, “wide”, and “outlier” Gaussians, each of the form

$$G(t_r,\sigma _{_{\mathrm{\Delta }t}})\frac{1}{\sqrt{2\pi }s\sigma _{_{\mathrm{\Delta }t}}}\mathrm{exp}\left(\frac{\left(t_rb\right)^2}{2(s\sigma _{_{\mathrm{\Delta }t}})^2}\right),$$
(7)
where $`s`$ and $`b`$ are parameters obtained from the fit to data. The coefficients $`f_i`$ of Eq. (6) satisfy $`f_w=1f_nf_o`$. The same $`\mathrm{\Delta }t`$ PDF parameters are used for signal and $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ events.

The $`\mathrm{\Delta }t`$ PDFs of the combinatoric $`B\overline{B}`$, peaking $`B^0\overline{B}^0`$, $`\overline{B}D^{}\rho ^{}`$, and continuum are of the form

$`𝒯_{\mathrm{Bgd}.}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ $`=`$ $`(1f_o){\displaystyle 𝑑\mathrm{\Delta }t_t\left[f_\tau \frac{1}{2\tau }e^{|\mathrm{\Delta }t_t|/\tau }+(1f_\tau )\delta (\mathrm{\Delta }t_t)\right]}`$ (8)
$`\times `$ $`\left[f_nG_n(t_r,\sigma _{_{\mathrm{\Delta }t}})+(1f_n)G_w(t_r,\sigma _{_{\mathrm{\Delta }t}})\right]+f_o{\displaystyle \frac{1}{\sqrt{2\pi }s_o}}\mathrm{exp}\left({\displaystyle \frac{\left(t_rb_o\right)^2}{2s_o^2}}\right),`$
where the phenomenological parameter $`\tau `$ is different from $`\tau _{_{B^0}}`$ of Eq. (6). The $`\delta (\mathrm{\Delta }t_t)`$ term accounts for events in which the $`\pi _h`$ originates from essentially the same point as the tracks dominating the determination of $`z_{\mathrm{other}}`$. Parameter values for each of the different background PDFs are determined from fits to independent control samples in data, as described in Sec. 3.6. The fraction $`f_o`$ of events corresponding to the outlier Gaussian is taken to be zero for the three $`B\overline{B}`$ background PDFs, based on studies performed with the Monte Carlo simulation and the data. In the continuum PDF, $`f_o`$ is determined to be about 1% for $`s_o=10`$ ps. In the peaking $`B^0\overline{B}^0`$ PDF $`f_\tau =0`$, reflecting the fact that the $`\pi _h`$ originates from the decay of the other $`B`$.

### 3.6 Fit Procedure

The $`B^0`$ lifetime $`\tau _{_{B^0}}`$ is obtained through a series of fits. First, the kinematic variable PDF parameters of $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$, combinatoric $`B\overline{B}`$ and the peaking $`B^0\overline{B}^0`$ background are determined by fitting the distributions of these variables in the Monte Carlo simulated events. The parameters of $`_{\mathrm{signal}}(F)`$, as well as $`f_{D^{}a_1}`$, and $`f_{\mathrm{peak}B^0}`$, are also obtained from the Monte Carlo simulation.

The $`(m(\rho ))`$, $`(m_{\mathrm{miss}})`$, and $`(m_{\mathrm{ES}})`$ parameters of signal and continuum events, and the $`(F)`$ parameters of continuum are obtained by fitting the kinematic variable distributions of the data in the signal region. This 4-dimensional fit is performed simultaneously for partially and fully reconstructed on-resonance data, and for off-resonance data. The fractions $`f_{q\overline{q}}`$ and $`f_{B\overline{B}}`$ are also determined in this fit, with $`f_{\mathrm{signal}}`$ obtained from $`_if_i=1`$. The value of $`f_D^{}`$ is set to 0 in this and the subsequent fits, and is later varied when studying systematic errors.

The parameters of $`𝒯_{B\overline{B}}`$ are determined by fitting the data in the $`m_{\mathrm{miss}}`$ sideband. The sideband is populated only by combinatoric $`B\overline{B}`$ and continuum events. Consequently, this fit uses $`F`$ as the only kinematic variable, and is performed simultaneously for on- and off-resonance data. The parameters of $`𝒯_{q\overline{q}}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ of this sample are also determined in the fit.

The composition of the wrong-sign event sample in the signal region and the parameters of $`𝒯_{\mathrm{peak}B^0}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ are determined from fits to this sample. The parameters of $`𝒯_{q\overline{q}}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ of this sample are also determined in the fit.

Finally, the signal region parameters of $`𝒯_{\mathrm{signal}}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ and $`𝒯_{q\overline{q}}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ are determined from a simultaneous fit to the right-sign signal region on-resonance, off-resonance and fully reconstructed data. The parameters of $`𝒯_{B\overline{B}}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ and $`𝒯_{\mathrm{peak}B^0}(\mathrm{\Delta }t,\sigma _{_{\mathrm{\Delta }t}})`$ are taken from the sideband and wrong-sign fits, respectively. Use of the sideband and wrong-sign samples for this purpose is validated using the Monte Carlo simulation.

The samples used to obtain parameters of the different $`\mathrm{\Delta }t`$ PDF components are summarized in Tab. 1.

## 4 Results

The partially reconstructed signal region on-resonance sample contains 50898 events, including $`5266\pm 251\pm 34`$ $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$ and $`691\pm 36\pm 4`$ $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ events, as determined by the kinematic variable fit. The systematic errors are due to the finite numbers of events in the Monte Carlo simulation samples used to obtain the kinematic variable distributions of the two $`B\overline{B}`$ backgrounds and $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$. The fully reconstructed sample contains $`255\pm 20`$ signal events.

Projections of the PDF onto the data are shown in Figs. 1 through 3. The result of the maximum likelihood $`\mathrm{\Delta }t`$ fit is

$$\tau _{_{B^0}}^{\mathrm{raw}}=1.535\pm 0.064(\mathrm{stat}.)ps,$$
(9)
where the error is statistical only.

Several corrections are applied to this result, in order to account for known sources of bias. A correction of $`+0.008\pm 0.011`$ ps is due to the assignment of $`a_1`$ daughter tracks to the other $`B`$ vertex, decreasing the measured $`\mathrm{\Delta }t`$ in $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ events. The resulting value of 1.543 ps is divided by $`R_D=0.982\pm 0.022`$, the ratio between the $`B^0`$ lifetime obtained from a fit to signal Monte Carlo events and the value obtained from a fit to the true $`\mathrm{\Delta }t_t`$ distribution of this sample. This correction accounts for the effect of $`D`$ daughter tracks that pass the cone cut and are used in the other $`B`$ vertex. A correction of $`+0.014\pm 0.013`$ ps is applied to this result, to account for a possible bias due to event selection, determined by fitting the true $`\mathrm{\Delta }t_t`$ distribution of signal events passing the selection criteria. The magnitudes and errors of all these corrections are obtained from the Monte Carlo simulation.

The fit PDF was used to generate and fit hundreds of Monte Carlo samples, each corresponding to the data sample in number of events and PDF parameters. The value of $`\tau _{_{B^0}}`$ obtained from these fits was on average lower than the generated value by $`0.031\pm 0.005`$ ps. Repeating these studies with different Monte Carlo sample sizes, this bias is understood to be due to limited sample statistics. A correction of this magnitude is therefore added to the value of $`\tau _{_{B^0}}`$. The fully corrected result is

$$\tau _{_{B^0}}=1.616\pm 0.064(\mathrm{stat}.)\mathrm{ps}.$$
(10)
## 5 Systematic Errors and Cross Checks

Several sources of systematic error are considered. The statistical error matrix obtained from the wrong-sign signal region $`\mathrm{\Delta }t`$ fit is used to vary the parameters of the peaking $`B^0\overline{B}^0`$ background, taking into account their correlations. A fit to the right-sign signal region data follows each variation in these background parameters. The resulting variations in $`\tau _{_{B^0}}`$ are added in quadrature to form the total systematic error due to the finite number of events in the wrong-sign sample. With the same procedure, the errors due to the sideband fit are propagated to the wrong-sign signal region and then to the right-sign signal region fits, to obtain the error due to the sideband sample size. The errors due to the finite number of events used in the kinematic variable fits on data and the Monte Carlo simulation are evaluated in the same way.

The Monte Carlo statistical errors in the determination of $`R_D`$, the $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ bias, and the selection bias corrections are taken into account. The fraction of events in which $`D`$ daughter tracks are used in the other $`B`$ vertex fit is varied by $`\pm 5\%`$. The magnitude of this variation is determined by comparing the $`N_{\mathrm{tr}}^D`$ distributions of fully reconstructed data and Monte Carlo events. The resulting variation in $`R_D`$ is used to evaluate the systematic error due to this uncertainty.

The contribution of the $`\overline{B}D^{}\rho ^{}`$ background is neglected in the fits. To evaluate the systematic error associated with this, we instead take the number of $`\overline{B}D^{}\rho ^{}`$ in the data sample to be 2400, corresponding to $`(\overline{B}D^{}\rho ^{})(D^{}D^+\pi )=0.3\%`$. This value is estimated from known branching fractions of the decays $`\overline{B}D^{}\pi ^{}`$, $`\overline{B}D^{()}\rho ^{}`$, $`\overline{B}D^{()}\pi ^{}`$, and available limits on $`(\overline{B}D^{}\rho ^{})`$ . The PDF parameters of this background are taken from the Monte Carlo simulation. Repeating the $`\mathrm{\Delta }t`$ fit yields a 0.023 ps change in the value of $`\tau _{_{B^0}}`$, which is taken as the systematic error. The $`D^{}`$ states simulated are $`D_1(2420)`$, $`D_2^{}(2460)`$, and $`D_1(j=\frac{1}{2})`$, the latter having mass 2.461 GeV and width 290 MeV. No significant difference is found between these states in terms of their effect on the observable quantities of this analysis.

Two variations of the signal $`\mathrm{\Delta }t`$ PDF are used in fits to the data. In one variation, the parameter $`b`$ in Eq. (7) is replaced by $`b\sigma _{_{\mathrm{\Delta }t}}`$. In the other, the sum of the narrow and wide Gaussians of Eq. (6) is replaced by a Gaussian convoluted with an exponential. The effect of generating Monte Carlo event samples using one PDF and fitting them using another PDF was studied. Based on these data and Monte Carlo studies, a systematic error of $`0.016`$ ps is estimated due to the choice of signal $`\mathrm{\Delta }t`$ PDF.

The parameters $`s`$ and $`b`$ (Eq. (7)) of the signal and continuum PDF outlier Gaussians are fixed in the fit to the right-sign signal region data. To estimate the associated systematic errors, their values are varied within reasonable ranges, and the resulting changes in $`\tau _{_{B^0}}`$ are taken as systematic errors.

Additional systematic errors are due to the uncertainty in the relative branching fractions of $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ and $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$, the level of peaking background, the introduction of a possible bias due to the use of fully reconstructed events, detector alignment and $`z`$-length calibration, and beam energy uncertainty. The total systematic error is 0.075 ps, dominated by the errors due to sideband and kinematic fit statistical errors, and Monte Carlo statistical errors. The systematic errors are listed in Tab. 2.

Several cross-checks were conducted to ensure the validity of the result. The number of signal events detected is in good agreement with the published branching fraction  and our signal reconstruction efficiency. The fit was repeated with different values of the cone cut, ranging between 0.6 and 1.2 radians. The data were fitted in bins of the lab frame polar angle, azimuthal angle, and momentum of the $`\pi _h`$, and in sub-samples corresponding to different SVT alignment calibrations. In all cases, no significant variation of the result was observed.

## 6 Conclusion

In a sample of 22.7 million $`B\overline{B}`$ pairs, we identified $`5521\pm 252\pm 34`$ $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$ and $`691\pm 36\pm 4`$ $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}a_1^{}`$ events using partial and full $`B`$ reconstruction. These events were used to measure the $`B^0`$ lifetime, with the preliminary result being

$$\tau _{_{B^0}}=1.616\pm 0.064(\mathrm{stat}.)\pm 0.075(\mathrm{syst}.)\mathrm{ps}.$$
(11)
This result is in good agreement with earlier published measurements , constituting a necessary step in validating the use of partially reconstructed $`\overline{B}{}_{}{}^{0}D_{}^{}{}_{}{}^{+}\rho ^{}`$ events for the measurement of $`\mathrm{sin}(2\beta +\gamma )`$.

Acknowledgements

We are grateful for the extraordinary contributions of our PEP-II colleagues in achieving the excellent luminosity and machine conditions that have made this work possible. The success of this project also relies critically on the expertise and dedication of the computing organizations that support BABAR. The collaborating institutions wish to thank SLAC for its support and the kind hospitality extended to them. This work is supported by the US Department of Energy and National Science Foundation, the Natural Sciences and Engineering Research Council (Canada), Institute of High Energy Physics (China), the Commissariat à l’Energie Atomique and Institut National de Physique Nucléaire et de Physique des Particules (France), the Bundesministerium für Bildung und Forschung (Germany), the Istituto Nazionale di Fisica Nucleare (Italy), the Research Council of Norway, the Ministry of Science and Technology of the Russian Federation, and the Particle Physics and Astronomy Research Council (United Kingdom). Individuals have received support from the A. P. Sloan Foundation, the Research Corporation, and the Alexander von Humboldt Foundation.


format: text

text:
# 1 Introduction

## 1 Introduction

There have been many attempts to explore the viability of weakly coupled supersymmetric string theory ground states with particle content roughly that of the minimal supersymmetric standard model . On the one hand, as reiterated in many recent precision phenomenological analyses, the trend in experimental data over many years overwhelmingly continues to favour theoretical particle-cosmology models that are close to minimal . Such models traditionally assumed a grand desert between the weak, or TeV, scale and the coupling unification scale, which is of order $`10^{16}`$ GeV. Moreover, the weak scale can be generated radiatively from the unification scale in good agreement with precision RG analysis of the flow of couplings in the minimal supersymmetric standard model with three generations and a heavy top quark. On the other hand, recent directions in braneworld phenomenology have explored the implications of large spatial dimensions , of warped spacetime metrics , of hierarchies from fluxes , and of split supersymmetry breaking : a wide variety of phenomenological scenarios, and where the string scale has been assumed to range anywhere from the GUT scale down to the TeV scale . The detailed analyses are far from conclusive and the debate is likely to remain controversial for some time to come. In this paper, we wish to simply point out that there is a mechanism within open and closed string theory that can alter the gauge coupling unification scale significantly relative to the fundamental closed string scale, $`m_s`$$`=`$$`\alpha ^{1/2}`$.

The key point is that open and closed string theories can couple to external electromagnetic background fields . Thus, the effective string tension in a vacuum with external electromagnetic background field is altered relative to its value in empty space . While this phenomenon is well-known in intersecting brane models , we wish to focus on its possible significance in the broader context of early Universe phenomenology. Consider the following generic setting for a 4D braneworld model describing our early Universe: a stack of intersecting Dbranes in the type IB string with standard model gauge group and particle spectrum realized on the worldvolume of the intersecting branes . We will examine such a braneworld model at finite temperature in the Euclidean time prescription . It is helpful to think of the gravitational sector of the thermal type IB string as providing a heat bath with which the ensemble of short open strings on the branevolume is in thermal equilibrium. We work with the canonical ensemble, in a fixed spatial volume $`V`$, and at fixed temperature $`1/\beta `$.

As shown in , the free open and closed string gas undergoes a continuous phase transition of the Kosterlitz-Thouless type at a temperature of order the string scale. At low temperatures, we have a gas of short open strings whose free energy scales as $`T^{p+1}`$. This is as expected, since the low energy field theory isolated in the short open string limit is a $`p`$$`+`$$`1`$-dimensional finite temperature gauge theory. The order parameter for the phase transition in the low energy finite temperature supersymmetric gauge theory is the coincidence limit, $`r`$$``$$`0`$, of the expectation value of a pair of timelike Wilson loops at fixed spatial separation $`r`$ which, as shown in  and more recently in , has a first-principles derivation from the worldsheet representation. The leading contribution is independent of string coupling and is given by a sum over oriented world-surfaces of cylindrical topology with boundaries mapped to a pair of fixed curves winding the Euclidean time direction. The leading contribution to the free energy, on the other hand, comes from both oriented and unoriented surfaces— with topology of the cylinder, Mobius strip, or Klein bottle, and it is independent of string coupling. The contribution from the tours vanishes , as shown in detail more recently in . In , we calculate the one-loop contributions to the free energy as well as to the short distance correlation function of a pair of timelike Wilson-Polyakov loops. The one-loop free energy turns out to vanish identically as a consequence of tadpole cancellation for the unphysical massless state in the Ramond-Ramond sector; a vanishing dilaton tadpole is another remarkable consequence. The remaining thermodynamic potentials are nonvanishing.

It should be stressed at the outset that the worldsheet analysis in  is restricted to the thermal behavior of the canonical ensemble of open and closed strings. All of our considerations are based on the oneloop vacuum amplitude at finite temperature which is independent of dependence on the string coupling. Thus, our results are expected to dovetail neatly with any nonperturbative analyses that may follow in the future. Although the phase transition itself lies well within the regime of validity for our one-loop calculation, we cannot follow the behavior of the long string phase to indefinitely high temperatures since string loop corrections, and consequently, gravitational interactions have not been examined thus far. Such interactions may, for example, indicate a further phase transition into a Schwarzschild black hole, but such phases are beyond the realm of our worldsheet analysis. They necessarily require an understanding of strong coupling effects. In addition, a formalism for the microcanonical string ensemble seems necessary for a fully convincing discussion . We emphasize that our analysis of the free energy of the string canonical ensemble in  is fully compatible with the analyticity of perturbative string amplitudes as a function of temperature; this property is simply a special case of the well-known analytic dependence on the moduli in any braneworld or string compactification. On the other hand, a description of a first-order phase transition in the low energy finite temperature supersymmetric gauge theory can be achieved if we combine the low energy limits of a pair of string theories linked by a thermal T-duality transformation, namely, type IB and type I. This phenomenon is elaborated in much more detail in our recent papers . Note that this provides an analytic description of either side of the phase boundary at a temperature of order the string scale.

In recent years it has become well-known that sub-string-scale short distance phenomena can be probed in an open and closed string theory with D0branes— pointlike topological string solitons whose mass scales as $`1/g`$, in the presence of a background electromagnetic field . The key point is the altered effective string mass scale in a vacuum with two-form background field. Notice that the pointlike D0branes behave like analogs of the infinitely massive heavy quarks of QCD. Guided by this analogy, we consider parallel timelike Wilson loops at fixed spatial separation $`r`$, lying in the worldvolume of intersecting Dbranes wrapped about the Euclidean coordinate $`X^0`$. The loops represent the Euclidean time world-histories of a pair of static, semiclassical heavy quarks: the endpoints of open string belong in the fundamental representation of the Yang-Mills gauge group. As shown in , in the simplest case of loops lying within the D9brane stacks of the $`O(16)`$$`\times `$$`O(16)`$ type IB ground state at finite temperature, an expression for this macroscopic loop amplitude can be derived from an extension of the usual Polyakov path integral over connected worldsurfaces. Thus, $`𝒲^{(2)}`$ is also computed from first principles using Riemann surface methodology, and it is obtained by summing worldsheets with the topology of an annulus, but with boundaries mapped to a pair of closed timelike loops, $`𝒞_i`$, $`𝒞_f`$, at fixed spatial separation $`r`$ in the embedding, target-space worldvolume of Dbranes . The result takes the form:

$`𝒲_2(\beta ,r)=`$ $`\underset{r0}{lim}{\displaystyle _0^{\mathrm{}}}𝑑t{\displaystyle \frac{e^{r^2t/2\pi \alpha ^{}}}{\eta (it)^8}}{\displaystyle \underset{n\mathrm{Z}}{}}q^{\pi ^2n^2\alpha ^{}/\beta ^2}`$ (1)
$`\times [({\displaystyle \frac{\mathrm{\Theta }_{00}(it;0)}{\eta (it)}})^4({\displaystyle \frac{\mathrm{\Theta }_{10}(it;0)}{\eta (it)}})^4`$ (2)
$`e^{ı\pi n}\{({\displaystyle \frac{\mathrm{\Theta }_{01}(it;0)}{\eta (it)}})^4({\displaystyle \frac{\mathrm{\Theta }_{11}(it;0)}{\eta (it)}})^4\}].`$ (3)
More generally, in the generic braneworld model, the sum within square brackets will take a more complicated form, in general incorporating a dependence on moduli other than $`\beta `$ characterizing the compact spatial coordinates. But the contribution from thermal modes will remain unchanged. The leading $`r`$ dependence of the short distance pair potential is extracted from the dimensionless amplitude $`𝒲_2`$ as follows. We set $`𝒲_2`$$`=`$$`lim_\tau \mathrm{}_\tau ^{+\tau }𝑑\tau V[r(\tau ),\beta ]`$, inverting this relation to express $`V[r,\beta ]`$ as an integral over the modular parameter $`t`$. Consider a $`q`$ expansion of the integrand, valid for $`t`$$``$$`\mathrm{}`$ where the shortest open strings dominate the modular integral. Retaining the leading terms in the $`q`$ expansion and performing explicit term-by-term integration over the worldsheet modulus, $`t`$, , isolates the following short-distance pairwise interaction :

$`V(r,\beta )=`$ $`(8\pi ^2\alpha ^{})^{1/2}{\displaystyle _0^{\mathrm{}}}𝑑te^{r^2t/2\pi \alpha ^{}}t^{1/2}`$ (4)
$`\times {\displaystyle \underset{n\mathrm{Z}}{}}(1616e^{i\pi n})q^{\alpha ^{}\pi ^2n^2/\beta ^2}+\mathrm{}`$ (5)
$`=`$ $`(8\pi ^2\alpha ^{})^{1/2}\mathrm{\Gamma }(3/2)r_{\mathrm{min}}^3{\displaystyle \frac{2^5}{r^3}}\left[1{\displaystyle \frac{3}{2}}{\displaystyle \underset{n=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{\beta _C^42^2(n+\frac{1}{2})^2}{\beta ^2r^2}}\right]+\mathrm{}.`$ (6)
We have expressed the result in terms of the characteristic minimum distance scale probed in the absence of external fields, $`r_{\mathrm{min}.}`$$`=`$$`2\pi \alpha ^{1/2}`$ , and the bosonic closed string’s self-dual inverse temperature, $`\beta _C`$$`=`$$`2\pi \alpha ^{1/2}`$ . At low temperatures, with $`\beta `$$`>>`$$`\beta _C`$, we can expand in a power series, and the leading correction to the inverse power law is $`O(\beta _C^4/\beta ^2r^5)`$. At high temperatures with $`\beta `$$`<<`$$`\beta _C`$, the potential takes the form obtained by a thermal duality transformation, a plausible signal indicating the onset of the the expected long string phase. This hint is investigated more carefully in the recent works . We give evidence of a first order deconfining phase transition in the low energy finite temperature supersymmetric gauge theory, extracting the high temperature behavior at temperatures far above the string scale from the low energy limit of the Euclidean T-dual, type I string theory. The transition temperature is string scale.222The precise normalization of the potential, and the transition temperature, is given in the recent work .

We now come to the main observation of this paper. In the presence of an external electromagnetic field, the result given above is modified by the simple replacements: $`r_{\mathrm{min}.}`$$``$$`2\pi \alpha ^{1/2}u`$, $`\beta _C`$$``$$`u\beta _C`$ where $`^{9j}`$$`=`$$`\mathrm{tanh}^1u`$ is the electromagnetic field strength, assumed to be constant for simplicity of calculation. The transition temperature, $`T_d`$$`=`$$`T_H/u`$, in the presence of an electromagnetic background is consequently shifted relative to the phase transition temperature in empty space, $`T_H`$$`=`$$`m_s/2\sqrt{2}\pi `$. Since we do not as yet have an understanding of the mechanism that might generate such an electromagnetic field at the string mass scale, the Wilsonian perspective suggests that we parameterize our ignorance by interpreting this as a generic consequence of an “effective” string mass scale, $`m_s/u`$, in spacetimes with a two-form background field . Clearly, whether one observes a lowering, or raising, of the string mass scale depends on the strength of the electromagnetic field. We should clarify that the statements above only invoke the leading correction to the effective string scale due to the background field as in . But it is, in fact, easy to obtain the exact electromagnetic field dependence of both the macroscopic string amplitude, and generic one-loop string scattering amplitudes, in a two-form background field of arbitrary strength, as has been shown in the papers .

Note Added (Dec 2004): Since the first appearance of this work, we have further clarified the nature of the deconfining thermal phase transition in the string canonical ensemble in our papers hep-th/0409301, and hep-th/0408206. Notice that the ensemble of short open strings in our scenario is in a state of thermal equilibrium at the effective string scale. The idea that a deconfining thermal phase transition might have occurred in the early Universe, accompanied by the formation of a cosmic string which is tentatively identified with a long winding mode in the theory of fundamental superstrings, appears in a 1988 paper by Englert, Orloff, and Piran .333This reference came to my notice just recently . An interesting point made in  is the apparent clash between the necessary conditions that must be met by cosmic string dynamics as required by galactic structure formation vs those required by a viable beyond-the-Standard-Model particle phenomenology. Our observation that an electromagnetic background impacts the constraints on the latter analysis in open and closed string theories may help in mitigating this clash, although we do not have anything remotely close to a satisfactory proposal for early Universe phenomenology at the moment. There has been considerable recent activity in exploring cosmic string dynamics in String/M theory , although within a different phenomenological framework that has focussed on the important issue of moduli stabilization . We should note that there is significant evidence for a micro-Gauss strength magnetic field in our Universe at the super-cluster distance scale, generally assumed by astrophysicists to be of primordial origin : can this be exploited to build a viable phenomenological model for the early Universe? The generation of primordial magnetic fields as seeds of galaxy formation has already played a significant role in the pre-Big-Bang Model scenarios of Veneziano and collaborators . We leave these as tantalizing, disparate, hints that may point to a more complete picture of the Early Universe within String/M theory in the future.

ACKNOWLEDGMENTS: I thank S. Shenker and M. Peskin for discussions in the early stages of this work, and M. Giovannini, S. Kachru, and D. Lust for more recent helpful comments. This research was funded in part by NSF-PHY-9722394.


text:
# Acknowledgements

## Acknowledgements

I thank E. Epelbaum and R. Machleidt for providing me tabulated deuteron wavefunctions.


text:
# Active Virtual Network Management Prediction: Complexity as a Framework for Prediction, Optimization, and Assurance

## 1 . Introduction

Kolmogorov Complexity ($`K(x)`$)  is the optimal compression of string $`x`$. This incomputable, yet fundamental property of information has vast implications in a wide range of applications including system management and optimization , security , and bioinformatics. Active networks  form an ideal environment in which to study the effects of tradeoffs in algorithmic and static information representation because an active packet is concerned with the efficient transport of both code and data. A question active network application developers must answer is: “How can I best leverage the capabilities that active networks have to offer?”. Because the word “active” in active networks refers to the ability to dynamically move code and modify execution of components deep within the network, this typically leads to another question: “What is the optimal proportion of content for an active application that should be code versus data?”. A method for obtaining the answer to this question comes from direct application of Minimum Description Length (MDL)  to an active packet. Let $`D_x`$ be a binary string representing $`x`$. Let $`H_x`$ be a hypothesis or model, in algorithmic form, that attempts to explain how $`x`$ is formed. Later in this paper, we view $`H_x`$ as a predictor of $`x`$ in the analysis of Active Virtual Network Management Prediction. For now let us focus on developing a measure of the complexity of $`x`$. MDL states that the sum of the length of the shortest encoding of a hypothesis about the model generating the string and the length of the shortest encoding of the string encoded by the hypothesis will estimate the Kolmogorov Complexity of string $`x`$, $`K(x)=K(H_x)+K(D_x|H_x)`$. Note that error in the hypothesis or model must be compensated within the encoding. A small hypothesis with a large amount of error does not yield the smallest encoding, nor does an excessively large hypothesis with little or with no error. A method for determining $`K(x)`$ can be viewed as separating randomness from non-randomness in $`x`$ by “squeezing out” non-randomness, which is computable, and representing the non-randomness algorithmically. The random part of the string, i.e. the part remaining after all pattern has been removed, represents pure randomness, unpredictability, or simply, error. Thus, the goal is to minimize $`l(H_e)+l(D_x|H_e)+l(E)`$ where $`l(x)`$ is the length of string $`x`$, $`H_e`$ is the estimated hypothesis used to encode the string ($`D_x`$) and $`E`$ is the error in the hypothesis. The more accurately the hypothesis describes string $`x`$ and the shorter the hypothesis, the shorter the encoding of the string. A series of active packets carrying the same information are measured as shown in Figure 1. Choosing an optimal proportion of code and data minimizes the packet length. The goal is to learn how to optimize the combination of communication and computation enabled by an active network. Clearly, if $`K(x)`$ is estimated to be high for the transfer of a piece of information, then the benefit of having code within an active packet is minimal. On the other hand, if the complexity estimate is low, then there is great potential benefit in including it in algorithmic form within the active packet. When this algorithmic information changes often and impacts low-level network devices, then active networking provides the best framework for implementing solutions (a specific example of separating non-randomness from randomness, although not explicitly stated as such, can be found in predictive mobility management as discussed in . However, the optimization of code/data or computation/communication has an additional constraint, namely security. Complexity also plays a significant role in the analysis of potential vulnerability within a network as discussed later in this paper.

An active packet that has been reduced to the length of the best estimate of the Kolmogorov Complexity of the information it transmits will be called the minimum size active packet. When the minimum size active packet is executed to regenerate string $`x`$, the $`D_x|H_e`$ portion of the packet predicts $`x`$ using static data ($`E`$) to correct for inaccuracy in the estimated hypothesis. There are interesting relationships among Kolmogorov Complexity, prediction, compression and the Active Virtual Network Management Prediction (AVNMP) mechanism described in . Details on the operation and mechanism of operation for AVNMP can be found in papers as early as . Space limitations in this paper preclude a detailed description of operation, however, an overview of the characteristics and properties of AVNMP as well as new experimental results are presented and the relationships among complexity, predictability, and compressibility and information assurance are discussed and experimentally validated throughout this paper. The next section provides an overview of AVNMP before discussing its relationship to Kolmogorov Complexity. After required relevant background on AVNMP is explained, the relationship to Complexity Theory is developed beginning from a high level overview, then driving down into detailed relationships and experimental results.

## 2 . Active Virtual Network Management Prediction Overview

The Active Virtual Network Management Prediction (AVNMP)111Current project progress and experimental code is maintained in http://www.crd.ge.com/~bushsf/ftn.This research has been funded by the Defense Advanced Research Projects Agency (DARPA) contract F30602-01-C-0182 and managed by the Air Force Research Laboratory (AFRL) Information Directorate. architecture provides a network prediction service that utilizes the capability of active networking to inject fine-grained models into the communication network to enhance network performance. Active Virtual Network Management Prediction (AVNMP) provides a network prediction service designed to facilitate the management of large, complex, active networks in a proactive manner. Network management includes a wide variety of responsibilities including configuration, fault, performance, accounting, and security management. A network management system must be able to monitor, control, and report upon the status of all these areas. In addition, the network management system should be more than a tool to generate reports and help fix problems, it should have the capability to anticipate and correct problems before they impact network performance. AVNMP accomplishes prediction and fault anticipation using a novel coupling of concepts from distributed simulation and active networking. A simple example demonstrating AVNMP results on a single node for load prediction is shown in Figure 2. In today’s management systems, a Management Information Base (MIB) maintains only current state values. In AVNMP, load is predicted into the future as real-time, called Wallclock, advances. Thus anticipated future values are available on the node as well as current values. In Figure 2, the Local Virtual Time (LVT) (future time), runs ahead of Wallclock Time (current time). Predicted load values are refined until Wallclock reaches the LVT of a particular value. This capability, described in detail in this paper, has been enabled by a new proactive network management framework combining three key enabling technologies; namely, distributed simulation, optimistic synchronization, and active networks.

The predictive capability provided by AVNMP facilitates the development of a variety of predictive applications from mobile wireless location management and network security to improved QoS. AVNMP provides an ideal predictive service for mobile systems to predict their location . Because mobile location can be predicted, hand-off situations are known ahead of time and setup for hand-off can take place prior to the hand-off event resulting in fast hand-off and improved QoS. In the domain of network security, AVNMP can anticipate the progress of an attack along most likely vulnerability paths and incorporate that information into decision-making. An attack can be propagated through the system before it actually occurs in order to determine its impact. In collaboration with the United States National Institute of Standards and Technology, AVNMP has been demonstrated with CPU prediction models showing the system’s ability to detect malicious active packets. Combined with the load prediction capability of AVNMP, Denial-of-Service attacks that use either abnormal amounts of CPU time or large numbers of small CPU packets can be detected and stopped . With regards to QoS, the load application previously discussed allows resources and routing to be better managed by anticipating traffic in order to optimize load distribution within the network. A few additional selected uses for AVNMP are the ability to choose an optimum management polling interval that minimizes overhead based upon predicted rate of change and fault probability of the monitored data in a managed entity, fault correction before the system is impacted and with time available to perform dynamic optimization of repair parts, service, and solution entities such as software agent or human co-ordination and optimal resource allocation and planning not only for load, but also for CPU utilization that becomes significant in active networks. AVNMP allows “What if…?” scenarios to become an integral part of the network and finally, AVNMP-enhanced components are enabled with the ability to protect themselves by taking proactive, evasive action, such as migrating to safe hardware before anticipated disaster occurs.

A severe limitation of state-of-the-art network management techniques is that they are inherently reactive. They attempt to isolate the problem and determine solutions after the problem has occurred. Proactive management is a necessary ingredient for managing future networks. Part of the proactive capability is provided by analyzing current performance and predicting future performance based on likely future events and the network’s reaction to those events. This can be a highly dynamic, intensely computational operation. This has prevented management software from incorporating prediction capabilities. But distributed simulation techniques take advantage of parallel processing of information. If the management software can be distributed, it is possible to perform computation in parallel and aggregate the results to minimize computation overhead at each of the network nodes. The usefulness of optimistic techniques has been well documented for improving the efficiency of simulations. In optimistic logical process synchronization techniques, also known as Time Warp , causality can be relaxed in order to trade model fidelity for speed. If the system that is being simulated can be queried in real time, prediction accuracy can be verified and measures taken to keep the simulation in line with actual performance. AVNMP is implemented in an active network to provide predictive management of an active network. AVNMP is designed to utilize the additional processing and flexibility of an active network to provide better management of the added complexity in processing and bandwidth in an active network. AVNMP requires extreme network flexibility, primarily in the ability to inject fine-grained component models into the network. A much less flexible version of AVNMP could be implemented in legacy systems by building dedicated network component models directly into legacy network devices such as today’s routers. However, these models would be immobile and not easily updated or removed, most likely requiring the network device to be taken down when models are changed or updated. A better mechanism for using AVNMP to manage legacy networks would be to provide an active network overlay capable of monitoring legacy nodes. AVNMP should reside in the active network overlay providing a predictive management service for the legacy network. This has the added benefit of transitioning a legacy network to an active network.

AVNMP, injected into the network as an active application, is capable of modeling load and propagating state information in a manner that meets the demand for accuracy at a particular active node. Greater demand for prediction accuracy is met at the cost of AVNMP performance, that is, the ability of AVNMP to predict farther into the future. While this paper focuses on network traffic and load prediction, an AVNMP application to predict CPU utilization for active network in collaboration with National Institute of Standards and Technology  has been demonstrated. The inherently distributed nature of communication networks and the computational power unleashed by the active networking paradigm have been used to mutual benefit in the development of the Active Virtual Network Management Prediction mechanism. The active network benefits from AVNMP by continuously receiving information about potential problems before they occur.

AVNMP benefits from the active network in many ways. The first, and most practical way is the ease of development and deployment of this novel prediction mechanism. This could not have been accomplished so quickly or easily given today’s closed, proprietary network device processing. Another benefit is the fact that network packets now have the unprecedented ability to control their own processing. Great advantage was taken of this new capability in AVNMP. Virtual messages, varying widely in content and processing, can adjust their predicted values as they travel through the network. Finally, active networks add a level of robustness that cannot be found in today’s networks. This robustness is due to the ability of AVNMP system components, which are active packets, to easily migrate from one node to another in the event of failure –or the prediction of failure provided by AVNMP itself.

The desired characteristics of AVNMP are a large lookahead time, high prediction accuracy, low overhead and robust operation. Each of these characteristics is inter-related and a suitable tradeoff needs to be determined during configuration of the system. The AVNMP experimental validation configuration for the initial test discussed in this paper is a feed forward network consisting of a host containing the Driving Process and four intermediate active network nodes containing Logical Processes as shown in Figure 3. AH-1 and AH-2 are host nodes and AN-1 through AN-5 are active network nodes. The edges between the nodes represent links between the labeled ports on each node. All nodes are Sun Sparcs running the Magician active network execution environment. The AVNMP system parameters were configured as shown in Table 1. In this experiment AVNMP is predicting the packet input and output rate for each link at each node, from an application residing on AH-1 that is transmitting an active audio packets.

The State Queue plot, Figure 2, shows the predicted traffic load values cached in the State Queue as a function of Local Virtual Time (LVT) and Wallclock. As Wallclock approaches any given Local Virtual Time, the predicted load values converge towards the actual load. The dashed line placed diagonally across the surface highlights where predicted time and actual time converge. The general operation is illustrated in the next five graphs where all measurements, unless otherwise indicated, are from node AN-4. These curves validate intuitive trends in the operation of AVNMP. Figure 4 shows the reduction in tolerance versus time that is pre-programmed into each Logical Process. The Y-axis is the tolerance that is demanded between the predicted value and the actual value of an Simple Network Management Protocol (SNMP) packet counter. This value is decreased purposely in this experiment in order to create a greater demand over time for accuracy and thus create a challenging validation of the AVNMP system under gradually increasing stress. In Figure 5 the proportion of out-of-tolerance messages is shown as a function of Wallclock. The Y-axis is the proportion of messages that arrived at a specific node out of tolerance, that is, the actual value exceeded the predicted value by an amount greater than the tolerance setting. As Wallclock progresses, the tolerance is purposely reduced causing a greater likelihood of messages exceeding the tolerance. This is done in order to validate the performance of the system as stress, in the form of greater demand for accuracy, is increased. Figure 6 shows the prediction error as a function of Wallclock. The Y-axis is the difference in the number of packets received versus the number of packets predicted to have been received. This graph verifies that the system is producing more accurate predictions as the demand for accuracy increases. However, the Y-axis of Figure 7 shows the lookahead decreasing versus Wallclock. The expected lookahead time is the difference between Wallclock and the Local Virtual Time at a particular node. The demand for greater accuracy reduces the distance into the future that the system can predict. Finally, in Figure 8, speedup, the ratio of virtual time to Wallclock of the real system, is shown as a function of Wallclock. The speedup is reduced as the demand for accuracy is increased. As previously mentioned, only for purposes of this experiment, the tolerance is being reduced as Wallclock progresses, causing the accuracy to increase while loosing performance in terms of speedup and lookahead.

### 2.1 . AVNMP Overhead

AVNMP has the potential to generate two forms of overhead, processing overhead and bandwidth overhead. If the predicted results are within the user specified error tolerance and the user fully utilizes the predicted results, then overhead is at a minimum. The question of overhead versus benefit becomes one that depends upon the perceived utility of predictive capability and depends significantly upon the manner and application in which it is used. It is the author’s belief that load and processing prediction are of particularly great importance in an active network where routing is based upon not only load, but the processing capability required by active applications. In this section, the load prediction application example is continued with overhead results displayed in terms of processing time and number of packets transmitted. The expected Active Network Encapsulation Protocol (ANEP)  packet size measured during this test was 1000 bytes.

#### 2.1.1 Task Execution Time and Message Overhead

The task execution time is the Wallclock time the system spends executing a non-rollback message. It was expected that task execution time would be essentially constant; however, it increases in direct proportion to the number of rollbacks as shown in Figure 9. This is caused by the lack of fossil collection. The increase in the number of values in the State Queue is causing access of the State Queue and Management Information Base (MIB) to slow in proportion to the queue size. Figure 10 displays the number of virtual messages versus Wallclock and Figure 11 displays the total number of anti-messages. This is expected to increase over time. This value is reset every time the tolerance is tightened (every 5 minutes in this case).

### 2.2 . AVNMP Robustness

AVNMP is both an active application and an application whose purpose is to provide predictive management of other active applications. As a management application it must be robust in the presence of a failing environment. So far, it has shown to provide graceful predictive degradation in the presence of dropped packets and broken links. AVNMP consists of two main types of active packets: AvnmpLP, which is the Logical Process, and AvnmpPacket, which is the virtual message. If an AvnmpLP packet is dropped, the destination node will not have the capability to work forward in time or forward virtual messages. Thus, AVNMP features will not be available on the node for which AvnmpLP was destined and the accuracy of other nodes may be reduced. If an AvnmpPacket is dropped or unexpectedly delayed, accuracy will be reduced because the State Queues of downstream nodes will lack a predicted value. However, AVNMP will continue to operate with degraded performance. In the next section the role of complexity in understanding prediction is discussed. Ideally, of course, AVNMP should have predicted the error condition and taken action to mitigate it. However, control mechanisms have not yet been implemented.

### 2.3 . Networking Viewed Through the Lens of Complexity

AVNMP can provide early warning of potential problems; however, the identification of a solution and marshaling of automated solution entities within an active network has not yet been fully addressed. This project has begun to lay the groundwork for such automated composition of management solutions within an active network . This direction is being carried forward by exploration of a relatively unexplored area -understanding the benefits of active networking, Algorithmic Information Theory, and its close companion, Complexity Theory. To our knowledge, this work is the first to propose and begin investigation into the newly available processing power of active networking through the concept of Complexity and Algorithmic Information (“Streptichrons”) as shown in Figure 12. Legacy networks, which are today’s passive networks, have been designed to optimize transmission of passive data using bit compression based upon the underlying notion of Shannon Entropy. AVNMP has shown that active networks allow for the possibility of executable models and that the corresponding information packets might be best studied with Kolmogorov Complexity as the underlying theory. It is serendipitous that Complexity Theory has been receiving more attention lately and is making significant theoretical progress at the same time that research into active networking is taking place. Active networks provide a new paradigm and enhanced capabilities, which, when combined with ideas from Algorithmic Information Theory , might lead to superior, innovative solutions to problems of network management. One possible approach proposes to combine Kolmogorov Complexity with the science of Algorithmic Information Theory (sometimes called Complexity Theory) to build self-managed networks that draw on fundamental properties of information to identify, analyze, and correct faults, as well as security vulnerabilities, in a distributed information system . Specifically, we suspect that complexity measures can be used to detect and analyze problems in a network, and to facilitate techniques to remedy network faults. We also envision that Kolmogorov Complexity can be applied directly to improve the performance of AVNMP. In general, complexity is not computable; however, the bounds on complexity tighten continuously as fundamental research in Kolmogorov Complexity progresses.

One potential drawback to AVNMP, gently pointed out earlier in this paper, is the fact that AVNMP itself consumes resources in an effort to predict resource usage in a network. Resource consumption by AVNMP is tied directly to accuracy: higher accuracy costs more in terms of bandwidth utilization, associated with simulation rollbacks and the concomitant transmission of anti-messages. Despite this relationship, potential exists to nearly reach the theoretical minimum amount of bandwidth to achieve maximal model accuracy. This possibility arises because AVNMP consists of many small, distributed models (each a description of a theory) that work together in an optimistic, distributed manner via message passing (data). Each AVNMP model can be transferred, using an active network, as a Streptichron , which is any message that contains an executable model in addition to data for prediction. Using Streptichrons, the optimal mix of data and model can be transmitted to implement MDL. Achieving maximal model accuracy at minimal bandwidth provides the best AVNMP accuracy at the least cost in AVNMP resource consumption.

Other possibilities exist to exploit Kolmogorov Complexity to improve AVNMP performance. For example, one can apply the MDL technique to the rollback frequency of all the AVNMP enhanced nodes in a network. A low rollback complexity (which suggests a high compressibility in the observed data) would indicate patterns in the rollback behavior that could be corrected relatively easily by tuning AVNMP parameters. High complexity (low compressibility) would indicate the lack of any computable patterns, and would suggest that little performance improvement could be achieved by simply tuning parameters. Thus, we hypothesize that our tuning gradient should be guided toward regions of high complexity, which suggests that we can tune parameters to improve the rollback frequency. The next section focuses upon experimental results relating prediction to complexity gathered from the operation of the AVNMP system.

### 2.4 . AVNMP and Kolmogorov Complexity

In AVNMP, information that impacts the network is transmitted based upon prediction at a low level within the network. Thus, AVNMP allows experimentation in defining the boundaries within which active networking is beneficial. In Figure 13 an active and passive form of AVNMP is represented. The passive case is represented in the upper portion of the figure. In the passive case, actual data ($`D_x`$) is observed at the Driving Process. Note that in the AVNMP architecture, Driving Processes exist at the edge of the system. They monitor external forces acting upon the system, such as load, and generate virtual messages, which are a short-term local prediction about a specific property such as input load, that are injected into the AVNMP system. The Driving Process has a hypothesis that has been formed about the data; predicted data ($`D_y`$) is generated in the form of static virtual messages. The term static indicates that information content within the message contains no executable code. The virtual messages are propagated through the network driving the the system ahead of Wallclock. When error in the hypothesis exceeds a preset threshold, AVNMP causes rollbacks to occur in order to adjust for the inaccuracy. In the lower portion of Figure 13, the hypothesis is included within each packet and is used to encode $`D_y`$ within the code portion of the active packet.

What is the relationship between the estimated operating hypothesis ($`H_e`$) that can encode an AVNMP packet and $`H_e`$ as the predictor in the Driving Processes? First, they are the same hypothesis. Second, it has been shown  that the shorter the packet, the better the predictor. Conversely, the worse the prediction, the longer the $`E`$ value, where $`E`$ can be considered any of the following equivalent names: error, complexity, or randomness within the AVNMP packet encoding. Can Active Virtual Network Management Prediction benefit from the fact that the smallest algorithmic form is also the most likely predictor of a sequence? This can come about because Driving Processes and Streptichrons (active virtual messages anticipating events in the future) benefit by being both small and accurate as shown in Figure 14. The objective is to increase the rate of convergence of the predictions held within the State Queue to converge to the actual value that will occur in the future, and to converge to that value before it actually exists. Actual and predicted values within a particular instance of a State Queue were shown in Figure 2. Let us examine AVNMP results in light of complexity in more detail in the next section.

### 2.5 . Load Prediction And Complexity In Active Virtual Network Management Prediction

With regard to active packets and information theory, passive data is simple Shannon compressed data, and active packets are a combination of data and program code whose efficiency can be estimated by means of Kolmogorov Complexity. The active network Kolmogorov Complexity estimator is currently implemented as a quick and simple compression estimation method. It returns an estimate of the smallest compressed size of a string. It is based upon computing the entropy of the weight of ones in a string. Specifically it is defined in Equation 1 where $`x\mathrm{\#}1`$ is the number of 1 bits and $`x\mathrm{\#}0`$ is the number of 0 bits in the string whose complexity is to be determined. Entropy is defined in Equation 2. See  for other measures of empirical entropy and their relationship to Kolmogorov Complexity. The expected complexity is asymptotically related to entropy as shown in Equation 3.

$`\widehat{K}(x)=l(x)H({\displaystyle \frac{x\mathrm{\#}1}{x\mathrm{\#}1+x\mathrm{\#}0}})+\mathrm{log}_2(l(x))`$ (1)
$`H(p)=p\mathrm{log}_2p(1.0p)\mathrm{log}_2(1.0p)`$ (2)
$`H(X)={\displaystyle \underset{l(x)=n}{}}P(X=x)K(x)`$ (3)
Load prediction data sampled from execution of AVNMP is analyzed relative to several hypotheses. The goal is to use a simple example to demonstrate the relationship among accuracy of hypotheses, complexity, and compression. The initial hypothesis ($`H_e`$) (regardless of naivete in choice of hypothesis) is that the data can be characterized by a simple linear extrapolation based upon the last sampled load values. This is shown in Figure 15 where the gray boxes are actual load samples and the black stars are predicted load samples. Note that the predicted load is based upon a short history shown in the graph as the initial match between predicted and actual load.

Various enhancements are added to the initial hypothesis to create new hypotheses for our test. In this specific case, a running average was used to smooth the data before the extrapolation. The size of the running average defines a hypothesis. Each enhancement is considered a new hypothesis ($`H_e`$) in this experiment. In Figure 16, for each $`H_e`$ the sum of the error in predictions is graphed as the gray boxes in the lower portion of the graph. The compressed size of the corresponding error is plotted as the black stars in the upper portion of the figure. Clearly a better hypothesis concerning the origination of the data results in better prediction and greater compression, while poor hypotheses result in inaccurate prediction and reduced compression. This provides a concrete demonstration of the relation between complexity and prediction accuracy.

A key contribution presented in this paper is the hypothesis and supporting experimental validation that greater complexity results in greater prediction error, and thus greater likelihood of AVNMP rollback. Load prediction error from AN-1 (see the experimental configuration shown in Figure 3) within the network is compared with the estimated complexity of the actual load. In Figure 17 the load prediction error is plotted with the estimated complexity versus Wallclock where values are taken over intervals of the same length as the Sliding Lookahead Window shown in Table 1. Larger error, and thus more likely rollback, occurs during periods of relatively high complexity, while complexity is low during periods of low prediction error.

As predictions become more inaccurate in AVNMP, virtual messages should slow down, rather than burden the system with potential rollbacks. Poorly predicted messages will naturally be larger in their minimum size, which slows down their rate of propagation in proportion to their inaccuracy.

Another issue concerns a mechanism for feedback to the Driving Process in order to improve $`H_e`$. Such a feedback mechanism can be based upon input from the complexity estimate, or minimum encoded packet size, of virtual messages. The hypothesis is adjusted in a manner that drives the system towards minimizing encoded virtual message size.

## 3 . Complexity and Assurance

Complexity is useful not only for management prediction and active packet length optimization, but also for security. The vulnerability analysis technique presented in this section takes into account the innovation of an attacker. A metric for innovation is not new; 700 years ago William of Occam suggested a technique . The salient point of Occam’s Razor and complexity-based vulnerability analysis is that the better one understands a phenomenon, the more concisely the phenomenon can be described. This is the essence of the goal of science: to develop theories that require a minimal amount of information to be fully described. Ideally, all the knowledge required to describe a phenomenon can be algorithmically contained in formulae, and formulae that are larger than necessary lack of a full understanding of the phenomenon. Consider an attacker as a scientist trying to learn more about his environment, that is, the target system. Parasitic computing  is a literal example of a scientist studying the operation of a communication network and utilizing it to his advantage in an unintended manner. In Parasitic computing, checksums, additional overhead supposedly designed to insure the integrity of the information, are turned against the system and used to the attacker’s advantage. In fact, because information assurance safeguard developers do not yet have a comprehensive conceptual framework in which to evaluate the effectiveness of their safeguards individually or as composites of safeguards, such scenes are unfortunately all too common. Safeguard designers must be able to capture and quantify the mechanism by which an attacker as scientist generates hypotheses and theorems about a system under attack. Theorems are attempts to increase understanding of a system by assigning a cause to an event, rather than assuming all events are randomly generated. If theorem $`x`$, described in bits, is of length $`l(x)`$, then a theorem of length $`l(m)`$, where $`l(m)`$ is much less than $`l(x)`$, is not only much more compact, but also $`2^{l(x)l(m)}`$ times more likely to be the actual cause than pure chance . Thus, the more compactly a theorem can be stated, the more likely the theorem is to be correct. A measure of this compactness is described and utilized in more detail later in this paper.

Imagine a vulnerability identification process that consists of the following: waiting for an information system to be attacked, then, assuming it survives and one can detect the attack, analyzing the attack, and if the information system is still not compromised, adding this information to one’s knowledge base. This technique would be unacceptable to most people, but it is essentially the technique used today. Information assurance, and vulnerability analysis in particular, are hard problems primarily because they involve the application of the scientific method by a defender to determine a means of evaluating and thwarting the scientific method applied by an attacker. This self-reference of scientific methods would seem to imply a non-halting cycle of hypothesis and experimental validation being applied by both offensive and defensive entities, each affecting the operation of the other. Information assurance depends upon the ability to discover the relationships governing this cycle and then quantifying and measuring the progress made by both an attacker and defender. The salient factor controlling the paths taken by attacker and defender are governed by the complexity of the system. Whether such properties are measurable and how they will behave in a complex system is a topic of open debate. However, a metric and framework are required for quantifying information assurance in such an environment of escalating knowledge and innovation. Progress in vulnerability analysis and information assurance research cannot proceed without fundamental metrics. The metrics should identify and quantify fundamental characteristics of information in order to guarantee assurance.

A fundamental definition of vulnerability analysis is formulated in this paper based upon attacker and defender as reasoning entities, capable of innovation. Truly innovative implementations of attack and defense lead to the evolution of complexity in an information system. Understanding the evolution of complexity in a system enables a better understanding of where to measure and how to quantify vulnerability and leads towards a calculus of information complexity. The design and implementation of a complexity-based vulnerability analysis technique is under development as a tool for automated measurement of information assurance. The motivation for complexity-based vulnerability analysis comes from the fact that complexity is a fundamental property of information and can be ubiquitously applied. The presentation and analysis of the Kolmogorov Complexity-based vulnerability analysis framework must accomplish several goals. As initially stated, the vulnerability analysis technique must demonstrate the ability to account for the innovation of an attacker. The technique should be based upon fundamental properties of information, rather than suffer from the combinatorial explosion that occurs when explicitly examining all possible events generated by specific systems. The vulnerability results should make intuitive sense; vulnerability is reduced by increasing the apparent complexity of access to information from potential attackers while increasing vulnerability for less complicated, or in some sense shortest paths of access to information. A topological view of vulnerability can be demonstrated. This is demonstrated by means of a Kolmogorov Complexity Map (K-Map) in which low complexity paths, which are likely to be easy for an attacker to follow, are identified. The concept of a K-Map, or complexity grid, is shown in Figure 18 and the K-Map for a specific example is derived later in this paper and shown in Figure 29. Figure 18 may itself appear quite complex upon first glance; however, focus upon individual parts of the figure in a logical progression. Begin with the information to be protected that lies at the bottom of Figure 18. Attacks are illustrated as the thin downward-pointing arrows attempting to penetrate the system in order to manipulate the information. Numerous safeguards, supposedly designed to protect the information, each designed to mitigate particular types of attack, are shown as barriers with various levels of porosity inserted across the middle of the figure. The overall complexity of the system is illustrated by the surface contour located above the information and safeguards and is comprised of the complexity of several entities, namely: the information itself, the complexity of the system in which the information resides and the complexity of the safeguards. Innovative attacks will be more likely to successfully penetrate areas of low complexity, easier to comprehend components of the system. In addition, specific types of attacks, such as Distributed Denial of Service (DDoS) will appear as warps in the complexity grid. This is due the inherent system correlation in DDoS attack-streams. The vulnerability analysis technique should be applicable in a highly dynamic and amorphous information environment; an active network environment is chosen because information can be transmitted through an active network while its proportion of algorithmic content varies. In other words, static data or executable code or various combinations of both can represent information; both forms of information should have high assurance. The assurance of their interaction at a low level within an active network presents a nice challenge.

Kolmogorov Complexity provides a measure of complexity that can be utilized for vulnerability analysis. Observe an input sequence at the bit-level and concatenate with an output sequence at the bit-level. This input/output concatenation is observed for either the entire system or for components of the system. Low complexity input/output observations quantify the ease of understanding by a potential attacker. Previous work has demonstrated the use of Kolmogorov Complexity for Distributed Denial of Service (DDoS) attack detection . Definition 1 explicitly states the means of measuring the complexity of a system component, or protocol interaction, to a potential attacker.

Vulnerability is inversely proportional to $`K(x[opstart:opend])/l(x[opstart:opend])`$ where $`opstart`$ is the bit at which an operation to be discovered within an information system begins, and $`opend`$ is the last bit in an attacker’s observation.

In the remainder of the paper, excerpts from a Mathematica Notebook are included. The excerpts contain code using common mathematical and programming constructs and therefore should be intuitively obvious without requiring knowledge specific to Mathematica; any Mathematica specific details are explained in the text. As a specific example of the algorithmic capabilities of active networks, consider the transmission of an estimate of $`\pi `$. One could choose to send $`\pi `$ as an extremely large number of digits; in contrast, one could send a smaller algorithm capable of generating $`\pi `$ to an arbitrary number of digits. Consider an illustration of this concept in more detail. The Mathematica code, $`\{\{\mathrm{\#}1/\mathrm{\#}2\&\}\},\{22.,7.\}\}`$, represents an unnamed function that divides the first argument by the second argument; the function implements $`22/7`$. Consider that the function ($`\{\{\mathrm{\#}1/\mathrm{\#}2\&\}\}`$) and the data ($`\{22.,7.\}`$) remain unevaluated and are transmitted together. This represents an active packet; it contains part code and part data. The RUN function evaluates the function and returns the result; the result in this case is static data, a legacy data packet. Mathematica code that analyzes the characteristics of algorithmic and passive information transmission is shown in Figure 19. The active packet is defined as $`\{\{\mathrm{\#}1/\mathrm{\#}2\&\}\},\{22.,7.\}\}`$, which contains a pair of values and the code necessary to perform division. The legacy, or passive packet, is defined as $`RUN\{\{\mathrm{\#}1/\mathrm{\#}2\&\}\},\{22.,7.\}\}`$, which pre-computes the result of the division and transmits the same information in non-algorithmic form. The argument defined as $`\{\{1,2,3,4\},\{4,3,2,1\}\}`$ identifies the links traversed by the active and passive packets respectively. In this case, the first packet begins by crossing link one and the second packet begins by crossing link four. The argument defined as $`\{100,100,1000,1000\}`$ indicates link capacities for links one, two, three, and four. Thus, the first packet transmits both code and data that generates the intended information, while the second packet transmits raw data only. The result of executing the function below is load and processing time spent on each link and node for each packet. In Figure 20, the load induced by sending the estimate of $`\pi `$ using AnetSim in Figure 20 is plotted for each link. Clearly, the algorithmic representation of the information is more compact and used less link capacity. In fact, this reinforces the fact that, by knowing how to compute $`\pi `$, one could build a more compact representation; this demonstrates Occam’s Razor for a useful purpose, information compression. This has facilitated study of active (algorithmic) versus passive transmission of information. For example, we allow the ratio of data to code to change for the same information as the packet traverses the network in a manner that optimizes both link capacity and node processor speed.

Before continuing with a specific analysis, consider Figure 24 which shows a topological view of components of a sample system under analysis. The nodes are active application components and the links are security relationships between the components; the links are quantified using Kolmogorov Complexity-based vulnerability analysis. START is a state that is outside the system that represents the state of the system before it has been penetrated by an attacker.

### 3.1 . Complexity Surface: The Kolmogorov Complexity Map

The General Electric Corporate Research and Development active network test bed implements complexity probes as part of the active execution environment. The choice was made to embed the complexity probe in the execution environment rather than as an active application because it is necessary to examine the content of active packets before they reach the execution environment. In the Mathematica simulation, each component of the active application contains probe-input points through which bit level input and output is collected. A complexity estimator based upon the simple inverse compression ratio from Equation 1 is used to estimate complexity in the density metric. Figure 21 graphs results from density estimates taken of accumulated input and output of three separate components of the active network application. The graph shows the complexity of bit-level input and output strings concatenated together. That is, every input sequence is concatenated with an output sequence and the density of the sequence is recorded at the bit-level. The input/output concatenation is generated either for individual components of the system of for a composition of components. If there is low complexity in the input/output observation pairs, then it is likely to be easy for an attacker to understand the system, as in Definition 1. The X-axis is the number of input and output observations concatenated to form a single string of bits. From Figure 21, it would appear that Component E is most vulnerable due to its consistently low complexity while Component B appears to be the least vulnerable due to its larger complexity. These results make intuitive sense because Component E simply forwards data without any form of protection while Component B adds noise to the data. This vulnerability method does not take into account whether a component reduces or increases complexity; in other words whether the change was endothermic or exothermic complexity. These results demonstrate how vulnerabilities are systematically discovered using complexity; vulnerabilities can be quantified to a value within the bounds of the complexity measure error.

In order to develop the Kolmogorov Complexity Map (K-Map), consider the topology in more detail. Figure 23 shows the resulting densities inserted into a Mathematica graph object. The graph object allows graph theory related analyses to be applied. The directed graph in Figure 24 shows the relationship among the vulnerabilities. The START state, located in the center of the topology, represents a location outside the system. In Figure 25 a matrix is generated that shows the cost, in terms of complexity, of traveling from any node to any other node in the K-Map.

In Figure 26 the function CoordVul computes a maximum flow through the K-Map graph using the node positions as shown in Figure 24. Density ($`K(x)/l(x)`$) from Definition 1, acts as a resistance, while its inverse acts as conductance, supporting insecurity flows as illustrated in Figure 28. The resulting flow matrix in Figure 27 shows the maximum flow through each link. Figure 29 shows the complexity surface of the resulting flows. Higher areas correspond to less vulnerable states, while lower areas correspond to more vulnerable states. Note that in the following contour maps, areas of infinite height are simply shown without a surface. By comparing Figure 24 and Figure 29, it is apparent that the START state, the infinite mountain in the center of the topology, is invulnerable, which makes intuitive sense. State E is the weakest individual component and lowest area on the right side. Note that while State C cannot be directly attacked from the START state, it can be attacked via states B and E, located in the upper and lower right side of the figure respectively, have a relatively intermediate level of vulnerability.

In the insecurity flow contour shown in Figure 30, the density from Definition 1 is resistance and all possible flows from and to every node are summed to obtain an insecurity level. While Node C is assigned infinite complexity as shown in Figure 29, it actually is the most insecure component given that flows exist from Nodes B and E.

## 4 . Summary

A Kolmogorov Complexity estimate was used within the Active Virtual Network Management Prediction framework in order to characterize and improve system performance. The application in this paper focused on an active network in which information, algorithmic and static, was transmitted to support prediction for active network management. However, the results are ubiquitously applicable to algorithmic transmission of information in general. Kolmogorov Complexity was experimentally validated as a theory describing the relationship between algorithmic compression, complexity, and prediction accuracy within an active network. Next the relationship between complexity and vulnerability analysis was proposed. Finally, this work sets the stage for research into self-composing solutions based upon Kolmogorov Complexity which will be the focus of the next phase of this project.

### 4.1 . Acknowledgments

The work discussed in this paper was funded in full by DARPA, under the auspices of the Fault Tolerant Networks program. Our thanks go to Doug Maughan, the Active Networks program manager and Scott Shyne, Air Force Rome Labs for their generous support.