# Photometric observations of flares on AD Leo from GWAC-F30 and TESS

Jian-Ying Bai  Key Laboratory of Space Astronomy and Technology, National
Astronomical Observatories, Chinese Academy of Sciences, Beijing 100101,
People’s Republic of China  Jing Wang  Key Laboratory of Space Astronomy and
Technology, National Astronomical Observatories, Chinese Academy of Sciences,
Beijing 100101, People’s Republic of China  Guangxi Key Laboratory for
Relativistic Astrophysics, School of Physical Science and Technology, Guangxi
University, Nanning 530004, People’s Republic of China  Hua-Li Li  Key
Laboratory of Space Astronomy and Technology, National Astronomical
Observatories, Chinese Academy of Sciences, Beijing 100101, People’s Republic
of China  Li-Ping Xin  Key Laboratory of Space Astronomy and Technology,
National Astronomical Observatories, Chinese Academy of Sciences, Beijing
100101, People’s Republic of China  Guang-Wei Li  Key Laboratory of Space
Astronomy and Technology, National Astronomical Observatories, Chinese Academy
of Sciences, Beijing 100101, People’s Republic of China  Yuan-Gui Yang  School
of Physics and Electronic Information, Huaibei Normal University, Huaibei
235000, People’s Republic of China  Jian-Yan Wei  Key Laboratory of Space
Astronomy and Technology, National Astronomical Observatories, Chinese Academy
of Sciences, Beijing 100101, People’s Republic of China  School of Astronomy
and Space Science, University of Chinese Academy of Sciences, Beijing,
People’s Republic of China

###### Abstract

We observed active M dwarf star AD Leo for 146 hr in photometry by GWAC-F30
and also analyzed 528-hr photometric data of the star from TESS. A total of 9
and 70 flares are detected from GWAC-F30 and TESS, respectively. Flare
durations, amplitudes and energies are calculated. The distributions of the
three properties and FFDs are given. Within the same energy range of flares,
the FFDs of AD Leo obtained in this research and the previous study are
basically consistent, which suggests that the magnetic activity of this star
has not significantly changed compared to that decades ago. Comparing with the
average FFD of M-type stars, AD Leo’s FFD is twice higher, indicating that its
magnetic activity is more active than that of the average level of the M-type.
Based on TESS light curve, AD Leo’s rotation period is calculated as
2.21${}^{+0.01}_{-0.01}$ day , supporting the result given in previous
research. During the decay phase of the most energetic flare from TESS, we
identified QPPs and determined a 26.5-min oscillation period, which is
currently the longest period for AD Leo, suggesting that long periodic
physical process existed during flare of this star.

Flare stars — Late-type dwarf stars — M type

##  1 Introduction

Stellar flares are violent explosion phenomena which lasts from a few seconds
to hours. During the explosion, a large amount of energies can be released
over a wide wavelength range, from radio to X-rays (Sanz-Forcada & Micela,
2002; Osten et al., 2006; Welsh et al., 2007; Osten et al., 2010; Davenport et
al., 2012). These energies are believed to come from magnetic reconnection
occurring in the stellar corona analogy to the Sun (Garcia Alvarez, 2000;
Tamazian et al., 2005; Benz & Güdel, 2010; Froning et al., 2019). Flares are
not only important for understanding star formation and evolution, but may
also help understanding the habitability evolution of planets around active
stars (e.g., Lammer et al., 2008, 2014a).

Several studies have suggested that stellar flares may be a possible threat
for a planet to maintain its habitable atmosphere (e.g., Segura et al., 2010;
Luger & Barnes, 2015; Tilley et al., 2019). Tilley et al. (2019) noted that
ultra-violet (UV) fluxes and energetic particles from frequent flares can
deplete ozone obviously, leading to a potentially uninhabitable planet. The
photoevaporation driven by extreme ultra-violet (EUV) and X-ray could lead to
erosion of atmosphere on low-mass planets (Lammer et al., 2013; Kislyakova et
al., 2013; Erkaev et al., 2016; Roettenbacher & Kane, 2017). Loyd et al.
(2018) indicates that stellar flares could dominate the far ultra-violet (FUV)
energy budget on M stars. In addition to flares, coronal mass ejections (CMEs)
may also erode a planet’s atmosphere, potentially lead to losing entire
atmosphere of one planet orbiting M star (Lammer et al., 2007, 2009, 2014b;
Wang et al., 2021).

AD Leo (GJ 388, BD +20 2465) is a bright active flare star (V = 9.52 mag),
with mass of 0.43 M☉, spectral type of M3 and distance of 4.9 pc (Keenan &
McNeil, 1989; Hunt-Walker et al., 2012; Bonfils et al., 2013; Buccino et al.,
2014; Lurie et al., 2014). Its radius is 0.436 ${}^{+0.049}_{-0.049}$ R☉ and
effective temperature is 3414 ${}^{+100}_{-100}$ K (Houdebine et al., 2016).
The metal abundance is 0.28 ${}^{+0.17}_{-0.17}$ and rotation period is
2.23${}^{+0.36}_{-0.27}$ days (Rojas-Ayala et al., 2012; Hunt-Walker et al.,
2012). Morin et al. (2008) suggests that AD Leo is seen nearly pole-on by a
spectropolarimetric study.

In this work, AD Leo are monitored in photometry for 146 hours. The Transiting
Exoplanet Survey Satellite (TESS; Ricker et al., 2014) also observed this star
from 2021-Nov-06 to 2022-Feb-26 photometrically. We analyzed these photometric
data. Flares are identified, and their properties are analyzed and discussed.
The paper is organized as follows. In Section 2, the observations and data
reduction are outlined. In Section 3, we describe the analysis method of the
data. The results and discussions are given in Section 4. In Section 5, we
provide a summary.

Date | Filter | Start | End | Duration
---|---|---|---|---
(UT) | (Johnson) | (UT) | (UT) | (Hour)
2021 Dec 25 | B | 15:11:12 | 19:25:47 | 4.24
2021 Dec 27 | B | 15:52:33 | 22:04:51 | 6.2
2021 Dec 28 | B | 15:48:20 | 21:35:31 | 5.79
2021 Dec 29 | B | 16:16:00 | 21:43:41 | 5.46
2021 Dec 30 | B | 15:45:49 | 21:40:05 | 5.9
2022 Jan 01 | B | 16:54:24 | 20:19:06 | 3.41
2022 Jan 03 | B | 16:45:51 | 20:07:48 | 3.37
2022 Jan 05 | B | 12:55:30 | 21:19:12 | 8.39
2022 Jan 06 | B | 16:30:25 | 21:59:59 | 5.49
2022 Jan 07 | B | 17:34:25 | 21:59:10 | 4.41
2022 Jan 08 | B | 18:15:33 | 19:44:09 | 1.48
2022 Jan 10 | B | 15:31:14 | 20:04:12 | 4.55
2022 Jan 12 | B | 17:02:29 | 20:26:01 | 3.39
2022 Jan 15 | B | 15:33:53 | 21:01:31 | 5.46
2022 Jan 16 | B | 18:27:46 | 22:12:23 | 3.74
2022 Jan 17 | B | 17:05:07 | 21:30:55 | 4.43
2022 Jan 25 | B | 15:45:34 | 19:26:04 | 3.67
2022 Jan 26 | B | 16:30:47 | 21:37:48 | 5.12
2022 Jan 27 | B | 15:32:55 | 20:39:56 | 5.12
2022 Jan 28 | B | 16:26:53 | 21:33:55 | 5.12
2022 Jan 29 | B | 18:00:56 | 22:18:38 | 4.29
2022 Feb 01 | B | 17:33:00 | 22:01:00 | 4.47
2022 Feb 02 | B | 18:27:27 | 21:48:57 | 3.36
2022 Feb 03 | B | 13:20:59 | 20:11:12 | 6.84
2022 Feb 04 | B | 16:28:16 | 21:56:01 | 5.46
2022 Feb 07 | B | 14:12:53 | 21:04:26 | 6.86
2022 Feb 08 | B | 13:58:49 | 20:48:52 | 6.83
2022 Feb 09 | B | 14:50:22 | 21:36:20 | 6.77
2022 Feb 10 | B | 13:57:49 | 20:47:52 | 6.83
Table 1:  Log of photometry by GWAC-F30

##  2 Observations and data reduction

AD Leo (RA 10:19:36.28, Dec +19:52:12.01) was observed by a 30-cm telescope
which is part of the Ground-Based Wide-Angle Camera (GWAC) network (Han et
al., 2021). GWAC network (GWAC-N) is part of the ground segment of the space-
based multi-band astronomical variable objects monitor (SVOM) mission (Wei et
al., 2016). The 30-cm telescope (GWAC-F30) is located at the Xinglong
Observatory of National Astronomical Observatories, Chinese Academy of
Sciences (NAOC) (Liu et al., 2022). It has a focal ratio of F/3.6, and is
equipped with a FLI camera (ProLine 16803) which contains a CCD with 4096
$\times$ 4096 pixels, providing a field of view of 1.9 $\times$ 1.9 degree2.
The pixel scale is 1.7 arcsec. A set of Johnson-Cousins UBVRI filters is
equipped for broadband photometry. The limiting magnitude in B band can reach
13.5 mag with signal-to-noise ratio (SNR) = 20 for 120 s of exposure.

In this work, AD Leo was monitored with B filter for 29 nights, from December,
2021 to February, 2022, $\sim$146 hr in total. The photometry log is shown in
Table 1, containing the observation date, filter applied, the start and end
times of each observing session and the session duration. The exposure time is
120 s and the dead time between two adjacent exposures is about 4 s, leading
to a cadence of 124 s for each observation session.

The images of the photometric observations are reduced using standard IRAF
111IRAF is distributed by the National Optical Astronomy Observatory, which is
operated by the Association of Universities for Research in Astronomy, Inc.,
under cooperative agreement with the National Science Foundation. routines,
including bias subtraction, dark subtraction and flat correction. We choose
2MASS J10194483+1953309 (RA 10:19:44.84, Dec +19:53:30.81) and BD+20 2464 (RA
10:19:36.34, Dec +19:53:42.00) as comparison and check stars respectively to
perform differential photometry. The top panel of Figure 1 shows all the light
curves of AD Leo observed by GWAC-F30.

AD Leo was also observed by TESS (Ricker et al., 2014) with 2-min cadence in
optical band during sector 45, 46 and 48. The TESS data is publicly available
from the Mikulski Archive for Space Telescopes (MAST
222https://archive.stsci.edu/missions-and-data/tess). Because of big noise in
sector 45 and 46, we only analysed the data of AD Leo from sector 48. The
Simple Aperture Photometry (SAP) and PreSearch Data Conditioned (PDC$\\_$SAP)
data are provided in TESS products. The PDC$\\_$SAP light curves are applied
in this work, in which long-term trends are removed but keeping short period
astrophysical signals. The bottom panel in Figure 1 presents TESS light curve
in sector 48 for AD Leo.

Figure 1: Light curves of AD Leo observed by GWAC-F30 and TESS. The top panel shows the data of GWAC-F30 in black points and the bottom presents that of TESS during sector 48 in gray. For both panels, the horizontal axis show the time in BJD - 2459500. The vertical axis of the top panel indicates differential magnitude in B band and that of the bottom is PDC$\\_$SAP flux of TESS.  Figure 2: The Raw LCV and the Residual LCV on 2022 January 1. The light curves of AD Leo are marked with black points and the light curve of the reference star with gray. In the top panel, the thick gray line traces the fit of smoothing average for the quiescent phase. In the bottom panel, the two black lines indicate the positions of 3 $\times$ SD (lower) and 5 $\times$ SD (higher), respectively. The arrow points out the identified flare.  Figure 3: Light curves of the flares observed by GWAC-F30. The arrows indicate the flares. The error bars present the photometry errors and they are smaller than black points in panel a and d.  Figure 4: Histograms of flare durations, amplitudes and energies. The vertical dotted lines signify the medians of these parameters. Flare | Trise | Tdecay | Ttotal | Amplitude | log Ebol
---|---|---|---|---|---
ID | (Minute) | (Minute) | (Minute) | (mag) |
1 | 16.48 | 51.52 | 68.00 | -0.960 $\pm$ 0.012 | 34.336 $\pm$ 0.005
2 | 2.06 | 4.12 | 6.18 | -0.055 $\pm$ 0.008 | 32.478 $\pm$ 0.003
3 | 2.06 | 6.18 | 8.24 | -0.031 $\pm$ 0.008 | 32.430 $\pm$ 0.003
4 | 2.06 | 6.12 | 8.18 | -0.074 $\pm$ 0.008 | 32.549 $\pm$ 0.003
5 | 2.48 | 9.04 | 11.52 | -0.082 $\pm$ 0.008 | 32.742 $\pm$ 0.003
6 | 2.07 | 20.67 | 22.74 | -0.372 $\pm$ 0.008 | 33.529 $\pm$ 0.003
7 | 2.06 | 4.12 | 6.18 | -0.063 $\pm$ 0.009 | 32.468 $\pm$ 0.004
8 | 12.32 | 22.67 | 34.99 | -0.17 $\pm$ 0.009 | 33.616 $\pm$ 0.004
9 | 2.06 | 6.12 | 8.18 | -0.054 $\pm$ 0.011 | 32.545 $\pm$ 0.004
Table 2:  Properties of the flares detected by GWAC-F30

##  3 Data Analysis

The light curves of AD Leo from GWAC-F30 and TESS are analyzed to detect
flares with a same program that has been applied in Bai et al. (2021). The
processing method of the program is briefly described here, more details can
be found in Bai et al. (2021). First, the light curve of AD Leo from single
night (Raw LCV) is fitted iteratively to remove outliers by smoothing average,
obtaining a quiescent phase (Hawley et al., 2014; Davenport et al., 2016; Yang
et al., 2017; Yang & Liu, 2019). Next, the Raw LCV is subtracted by the
quiescent phase in order to get a residual light curve (Residual LCV).
Finally, the Residual LCV is analyzed to identify flare candidates with the
similar criteria used in previous studies (see Fig. 2) (e.g., Hawley et al.,
2014; Bai et al., 2021). The criteria are listed as follows: (1) The light
curve of a flare candidate contains three consecutive measurements; (2) The
measurements are more than three times the standard deviation (SD) of the
quiescent phase, and at least one of them is more than five times the SD.
After applying the criteria, the profile of the light curve for each candidate
is also examined by visual inspection to confirm it consists of an impulsive
rise (relatively short) and an exponential decay (relatively long). Figure 3
presents the flare light curves observed by GWAC-F30.

Figure 5: Cumulative flare frequency versus flare energy of GWAC-F30 and TESS.
For GWAC-F30, the red circles represent the cumulative flare frequency of each
flare energy, and gray circles for TESS. The red and gray lines trace the
least-squares power-law fit. The vertical error bars illustrate standard
errors. Figure 6: Comparison of AD Leo’s FFDs in this work (red and gray
lines) with that of the same star obtained in Gershberg & Shakhovskaia (1983)
(dotted line) and the average FFD of 446 M stars getted from Günther et al.
(2020) (dash-dot line).

Cumulative flare frequency distribution (FFD) presents the relationship of
energies and burst rates of flares (Gershberg, 1972; Lacy et al., 1976; Hunt-
Walker et al., 2012; Paudel et al., 2018). To determine the bolometric flare
energies, we assume flare temperature is about 12000 K (Rigney et al., 2022).
The fraction of the flux falls within the B band is calculated as about 0.15,
and for TESS band is about 0.14 which is same with that applied in previous
research (Schmitt et al., 2019; Rigney et al., 2022). The bolometric flare
energies are calculated as B-band or TESS-band flare energies divided by the
fractions in corresponding band. Both the flare energy in B or TESS band are
obtained by the equivalent duration (Gershberg, 1972) of the flare multiplied
by the quiescent luminosity of AD Leo following the method described in Hawley
et al. (2014). The equivalent duration is defined as the time it takes for a
star to release the same amount of energy at quiescent stage as it releases
during a flare. It is computed as the time integral of Ff(t)/F0, where Ff(t)
is the flux of the flare and F0 is the flux of the star in the quiescent state
(see Gershberg, 1972; Hunt-Walker et al., 2012; Hawley et al., 2014). The
B-band flux of AD Leo is obtained by convolving the transmission of B filter
with the quiescent spectrum of the star taken from Cincunegui & Mauas (2004).
The quiescent luminosity in B band is obtained with 4$\pi$d2 multiplied by the
B-band flux of the quiescent state of AD Leo, where d is 4.9 pc (Gray &
Johanson, 1991). AD Leo’s quiescent luminosity in B band is calculated as 3.73
$\times$ 1030 erg s-1, and then the quiescent luminosity in TESS band is
obtained as the quiescent luminosity of B band divided by 0.15 and then
multiplied by 0.14. The errors of the flare energies are computed with the
photometry errors. The flare amplitudes, times of rise and decay, and the
total duration are also calculated (see Table 2).

To determin AD Leo’s rotation period, the TESS light curve is analyzed by the
PDM function in IRAF, which is based on the Phase Dispersion Minimization
method (Stellingwerf, 1978). We also analyse the decay phase of the largest
flare in TESS data to determin the period of quasi-periodic pulsations(QPP;
Zimovets et al. (2021)). The top panel of Figure 8 shows the light curve of
the strongest flare and the best fitting line to the decay stage. The decay
phase is fitted by the function f(x)=A1*exp(-x/T1)+A2*exp(-x/T2)+A3, in which
x and f(x) are the time and flux for each data point in light curve,
respectively, and the other terms in the function are fitting parameters. And
then, the fitting line is subtracted from the decay phase, obtaining the
resiudual light curve (middle panel of Figure 8). In order to get the QPP
period, the Lomb-Scargle method (Zechmeister & Kürster, 2009) is applied to
process the residual light curve. The power-period diagram is shown in bottom
panel of Figure 8.

Figure 7: Phase-folded light curve from TESS with the rotation period of 2.21
day for AD Leo. Figure 8: Top: The flare light curve with QPPs from TESS
(black dot). The gray line dnotes the best fitting of the flare decay phase.
Middle: Residual light curve of the flare decay stage subtracted by the
fitting line. Bottom: Power-period diagram calculated with the Lomb–Scargle
method.

##  4 Results and discussions

During the photometry observations of 146 hr to AD Leo by GWAC-F30 and 528 hr
by TESS, a total of 9 and 70 flares are identified, respectively, with the
method given in Section 3. Figure 3 gives light curves of the flares from
GWAC-F30, and the flares in panel (f) and (g) are also identified in TESS
data. The panel (a) of Figure 3 shows the light curve of the strongest flare
detected by GWAC-F30 which obviously involves two different processes in the
rise phase, slow and rapid rise. The two different processes may be dominated
by emission-line and continuum radiations, respectively (Bopp & Moffett,
1973). Table 2 lists the parameters of each flare from GWAC-F30, including the
flare ID, the times of the rise and decay, the total duration, the peak
amplitude in magnitude and the energy. For the flares detected from TESS data,
Figure 4 shows their distributions of durations, amplitudes and energies, and
the median values of the three parameters are 28.0 min, 4.3 mmag and 1032.5
erg, respectively. The temperatures of flares in panel (f) and (g) of Figure 3
are calculated as about 38000 and 9700 K, respectively.

Figure 5 displays the AD Leo’s FFD and the fitting lines of GWAC-F30 and TESS.
The FFDs are fitted by the least-squares power law of log(Flare frequency) =
–0.44${}^{+0.15}_{-0.15}$ log(Ebol) + 12.91${}^{+4.30}_{-4.30}$ and log(Flare
frequency) = –0.78${}^{+0.09}_{-0.09}$ log(Ebol) + 23.96${}^{+2.86}_{-2.86}$,
respectively. It is noted that the FFD slope of GWAC-F30 is smaller than that
of TESS, which is probably due to the lower detection limit of GWAC-F30 than
that of TESS. We also computed flare energies detected in the data of B-band
and TESS-band in different continuum temperatures(10000, 20000 and 30000 K),
to compare FFDs between B band and TESS band. The discrepancy, as shown in
Figure 5, between FFDs of the two bands is becoming smaller as the temperature
rises, suggesting that the discrepancy is correlated to the selected
temperature.

Figure 6 shows the FFDs of AD Leo, within the same energy range, calculated by
this work and obtained from Gershberg & Shakhovskaia (1983) which identified
25 B-band flares in 1010-hr photometric observations with a 64-cm telescope,
and the average FFD of 446 M-type flare stars from Günther et al. (2020). The
FFDs of AD Leo from different observations are basically consitent, and it is
apparent that the FFDs are higher than that of the average, indicating the
magnetic activity on AD Leo is more active than the average activity level of
these M-type stars.

Based on TESS light curve, the rotation period is determined as
2.21${}^{+0.01}_{-0.01}$ day, which is consistent with that (about 2.23 day)
given in previous research (e.g., Morin et al., 2008; Hunt-Walker et al.,
2012; Tuomi et al., 2018). Figure 7 indicates the phase diagram of AD Leo with
the period of 2.21 day. Several studies have indicated that the M-type flare
stars with shorter rotation periods present higher flare activity (e.g., Lin
et al., 2019; Yang & Liu, 2019). The rapid rotation may be the cause of the
active flare activity on AD Leo. Together with that AD Leo is seen nearly
pole-on, the FFD result supports that this star may has more opportunities to
observe CMEs (Morin et al., 2008; Muheki et al., 2020). In addition to the
rotation cycle, Buccino et al. (2014) pointed out that AD Leo may have two
longer chromospheric activity cycles by analyzing spectral and photometric
data, approximately seven and two years, which are explained by two dynamo
mechanisms acting near the surface and deep chroposphere, respectively.

Using the Lomb–Scargle method, we analyzed the decay phase of the strongest
flare on AD Leo in TESS data. QPPs with multiple cycles are well seen in the
residual light curve as shown by the middle panel of Figure 8. The bottom
panel in Figure 8 presents the power-period diagram, and an oscillation period
of 26.5 min is determined for the QPPs. The phenomenon of QPPs have been
detected both in solar and stellar flares, at least fifteen models are
developed to explain the phenomenon in solar flares(see review Zimovets et
al., 2021), but which one is closest to reality is still unknown. Up to now,
multiple researches have found QPPs during flares of AD Leo and the QPP
periods range from seconds to several minutes (Bastian et al., 1990; Houdebine
et al., 1993; Lovkaya, 2013). For AD Leo, the QPPs detected in our study has
the longest period. By analysing the short-cadence data of Kepler mission,
Pugh et al. (2016) finds that QPPs period are uncorrelated with stellar
parameters and flare energies, indicating that the QPPs are independent of
global properties of stars.

##  5 Summary

AD Leo was observed by GWAC-F30 in B bandpass from December, 2021 to February,
2022, obtaining 146-hr photometric data. The photometric data in sector 48
from TESS were also analyzed. A total of 9 and 70 flares are detected in
GWAC-F30 and TESS data, respectively. Flare duration, amplitude and energies
are calculated, and the distribution of the three properties and the FFDs are
given. The FFD of AD Leo is obtained from previous research in which 1010-hr
photometric data in B band is analyzed. Within the same flare energy range,
the FFDs of AD Leo obtained by GWAC-30, TESS and the previous study are
basically consistent. The average FFD of 446 M-type stars is obtained from
previous study in which the author identified and analyzed flares based on
TESS data. AD Leo’s FFD is significantly higher than the average FFD of
M-type, which suggests that the star’s magnetic activity is more active than
that of the average level of these M-type stars. We determined AD Leo’s
rotation period as 2.21${}^{+0.01}_{-0.01}$ day by analyzing TESS light curve,
and the period is consistent with that given in previous research. The rapid
rotation may be the cause for AD Leo’s active flare activity. During the decay
phase of the most energetic flare of TESS, we identified the QPPs and
determined the oscillation period of 26.5 min which is currently the longest
one for AD Leo.

This research is supported by the National Natural Science Foundation of China
(Grant No. 12133003, U1831207, U1938201 and 11973055) and the Strategic
Pionner Program on Space Science, Chinese Academy of Sciences (Grant No.
XDA15052600). This paper includes data collected by the TESS mission, which
are publicly available from the Mikulski Archive for Space Telescopes (MAST).
Funding for the TESS mission is provided by NASA’s Science Mission
directorate.

## References

  * Bai et al. (2021) Bai, J.-Y., Esamdin, A., Gao, X., Yan, Y., & Ren, J.-J. 2021, Research in Astronomy and Astrophysics, 21, 007, doi: 10.1088/1674-4527/21/1/7
  * Bastian et al. (1990) Bastian, T. S., Bookbinder, J., Dulk, G. A., & Davis, M. 1990, ApJ, 353, 265, doi: 10.1086/168613
  * Benz & Güdel (2010) Benz, A. O., & Güdel, M. 2010, ARA&A, 48, 241, doi: 10.1146/annurev-astro-082708-101757
  * Bonfils et al. (2013) Bonfils, X., Delfosse, X., Udry, S., et al. 2013, A&A, 549, A109, doi: 10.1051/0004-6361/201014704
  * Bopp & Moffett (1973) Bopp, B. W., & Moffett, T. J. 1973, ApJ, 185, 239, doi: 10.1086/152412
  * Buccino et al. (2014) Buccino, A. P., Petrucci, R., Jofré, E., & Mauas, P. J. D. 2014, ApJ, 781, L9, doi: 10.1088/2041-8205/781/1/L9
  * Cincunegui & Mauas (2004) Cincunegui, C., & Mauas, P. J. D. 2004, A&A, 414, 699, doi: 10.1051/0004-6361:20031671
  * Davenport et al. (2012) Davenport, J. R. A., Becker, A. C., Kowalski, A. F., et al. 2012, ApJ, 748, 58, doi: 10.1088/0004-637X/748/1/58
  * Davenport et al. (2016) Davenport, J. R. A., Kipping, D. M., Sasselov, D., Matthews, J. M., & Cameron, C. 2016, ApJ, 829, L31, doi: 10.3847/2041-8205/829/2/L31
  * Erkaev et al. (2016) Erkaev, N. V., Lammer, H., Odert, P., et al. 2016, MNRAS, 460, 1300, doi: 10.1093/mnras/stw935
  * Froning et al. (2019) Froning, C. S., Kowalski, A., France, K., et al. 2019, ApJ, 871, L26, doi: 10.3847/2041-8213/aaffcd
  * Garcia Alvarez (2000) Garcia Alvarez, D. 2000, Irish Astronomical Journal, 27, 117
  * Gershberg (1972) Gershberg, R. E. 1972, Ap&SS, 19, 75, doi: 10.1007/BF00643168
  * Gershberg & Shakhovskaia (1983) Gershberg, R. E., & Shakhovskaia, N. I. 1983, Ap&SS, 95, 235, doi: 10.1007/BF00653631
  * Gray & Johanson (1991) Gray, D. F., & Johanson, H. L. 1991, PASP, 103, 439, doi: 10.1086/132839
  * Günther et al. (2020) Günther, M. N., Zhan, Z., Seager, S., et al. 2020, AJ, 159, 60, doi: 10.3847/1538-3881/ab5d3a
  * Han et al. (2021) Han, X., Xiao, Y., Zhang, P., et al. 2021, PASP, 133, 065001, doi: 10.1088/1538-3873/abfb4e
  * Hawley et al. (2014) Hawley, S. L., Davenport, J. R. A., Kowalski, A. F., et al. 2014, ApJ, 797, 121, doi: 10.1088/0004-637X/797/2/121
  * Houdebine et al. (1993) Houdebine, E. R., Foing, B. H., Doyle, J. G., & Rodono, M. 1993, A&A, 274, 245
  * Houdebine et al. (2016) Houdebine, E. R., Mullan, D. J., Paletou, F., & Gebran, M. 2016, ApJ, 822, 97, doi: 10.3847/0004-637X/822/2/97
  * Hunt-Walker et al. (2012) Hunt-Walker, N. M., Hilton, E. J., Kowalski, A. F., Hawley, S. L., & Matthews, J. M. 2012, PASP, 124, 545, doi: 10.1086/666495
  * Keenan & McNeil (1989) Keenan, P. C., & McNeil, R. C. 1989, ApJS, 71, 245, doi: 10.1086/191373
  * Kislyakova et al. (2013) Kislyakova, K. G., Lammer, H., Holmström, M., et al. 2013, Astrobiology, 13, 1030, doi: 10.1089/ast.2012.0958
  * Lacy et al. (1976) Lacy, C. H., Moffett, T. J., & Evans, D. S. 1976, ApJS, 30, 85, doi: 10.1086/190358
  * Lammer et al. (2013) Lammer, H., Erkaev, N. V., Odert, P., et al. 2013, MNRAS, 430, 1247, doi: 10.1093/mnras/sts705
  * Lammer et al. (2008) Lammer, H., Terada, N., Kulikov, Y. N., et al. 2008, in Astronomical Society of the Pacific Conference Series, Vol. 384, 14th Cambridge Workshop on Cool Stars, Stellar Systems, and the Sun, ed. G. van Belle, 303
  * Lammer et al. (2007) Lammer, H., Lichtenegger, H. I. M., Kulikov, Y. N., et al. 2007, Astrobiology, 7, 185, doi: 10.1089/ast.2006.0128
  * Lammer et al. (2009) Lammer, H., Bredehöft, J. H., Coustenis, A., et al. 2009, A&A Rev., 17, 181, doi: 10.1007/s00159-009-0019-z
  * Lammer et al. (2014a) Lammer, H., Schiefer, S.-C., Juvan, I., et al. 2014a, Origins of Life and Evolution of the Biosphere, 44, 239, doi: 10.1007/s11084-014-9377-2
  * Lammer et al. (2014b) Lammer, H., Stökl, A., Erkaev, N. V., et al. 2014b, MNRAS, 439, 3225, doi: 10.1093/mnras/stu085
  * Lin et al. (2019) Lin, C. L., Ip, W. H., Hou, W. C., Huang, L. C., & Chang, H. Y. 2019, ApJ, 873, 97, doi: 10.3847/1538-4357/ab041c
  * Liu et al. (2022) Liu, H.-Y., Wang, X.-G., Xin, L.-P., et al. 2022, Research in Astronomy and Astrophysics, 22, 065002, doi: 10.1088/1674-4527/ac65e6
  * Lovkaya (2013) Lovkaya, M. N. 2013, Astronomy Reports, 57, 603, doi: 10.1134/S1063772913080040
  * Loyd et al. (2018) Loyd, R. O. P., France, K., Youngblood, A., et al. 2018, ApJ, 867, 71, doi: 10.3847/1538-4357/aae2bd
  * Luger & Barnes (2015) Luger, R., & Barnes, R. 2015, Astrobiology, 15, 119, doi: 10.1089/ast.2014.1231
  * Lurie et al. (2014) Lurie, J. C., Henry, T. J., Jao, W.-C., et al. 2014, AJ, 148, 91, doi: 10.1088/0004-6256/148/5/91
  * Morin et al. (2008) Morin, J., Donati, J. F., Petit, P., et al. 2008, MNRAS, 390, 567, doi: 10.1111/j.1365-2966.2008.13809.x
  * Muheki et al. (2020) Muheki, P., Guenther, E. W., Mutabazi, T., & Jurua, E. 2020, A&A, 637, A13, doi: 10.1051/0004-6361/201936904
  * Osten et al. (2006) Osten, R. A., Hawley, S. L., Allred, J., et al. 2006, ApJ, 647, 1349, doi: 10.1086/504889
  * Osten et al. (2010) Osten, R. A., Godet, O., Drake, S., et al. 2010, ApJ, 721, 785, doi: 10.1088/0004-637X/721/1/785
  * Paudel et al. (2018) Paudel, R. R., Gizis, J. E., Mullan, D. J., et al. 2018, ApJ, 858, 55, doi: 10.3847/1538-4357/aab8fe
  * Pugh et al. (2016) Pugh, C. E., Armstrong, D. J., Nakariakov, V. M., & Broomhall, A. M. 2016, MNRAS, 459, 3659, doi: 10.1093/mnras/stw850
  * Ricker et al. (2014) Ricker, G. R., Winn, J. N., Vanderspek, R., et al. 2014, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 9143, Space Telescopes and Instrumentation 2014: Optical, Infrared, and Millimeter Wave, ed. J. Oschmann, Jacobus M., M. Clampin, G. G. Fazio, & H. A. MacEwen, 914320, doi: 10.1117/12.2063489
  * Rigney et al. (2022) Rigney, J., Ramsay, G., Carley, E. P., et al. 2022, MNRAS, 516, 540, doi: 10.1093/mnras/stac2143
  * Roettenbacher & Kane (2017) Roettenbacher, R. M., & Kane, S. R. 2017, ApJ, 851, 77, doi: 10.3847/1538-4357/aa991e
  * Rojas-Ayala et al. (2012) Rojas-Ayala, B., Covey, K. R., Muirhead, P. S., & Lloyd, J. P. 2012, ApJ, 748, 93, doi: 10.1088/0004-637X/748/2/93
  * Sanz-Forcada & Micela (2002) Sanz-Forcada, J., & Micela, G. 2002, A&A, 394, 653, doi: 10.1051/0004-6361:20021158
  * Schmitt et al. (2019) Schmitt, J. H. M. M., Ioannidis, P., Robrade, J., Czesla, S., & Schneider, P. C. 2019, A&A, 628, A79, doi: 10.1051/0004-6361/201935374
  * Segura et al. (2010) Segura, A., Walkowicz, L. M., Meadows, V., Kasting, J., & Hawley, S. 2010, Astrobiology, 10, 751, doi: 10.1089/ast.2009.0376
  * Stellingwerf (1978) Stellingwerf, R. F. 1978, ApJ, 224, 953, doi: 10.1086/156444
  * Tamazian et al. (2005) Tamazian, V. S., Melikian, N. D., Karapetian, A. A., & Natsvlishvili, R. S. 2005, Astrophysics, 48, 279, doi: 10.1007/s10511-005-0027-2
  * Tilley et al. (2019) Tilley, M. A., Segura, A., Meadows, V., Hawley, S., & Davenport, J. 2019, Astrobiology, 19, 64, doi: 10.1089/ast.2017.1794
  * Tuomi et al. (2018) Tuomi, M., Jones, H. R. A., Barnes, J. R., et al. 2018, AJ, 155, 192, doi: 10.3847/1538-3881/aab09c
  * Wang et al. (2021) Wang, J., Xin, L. P., Li, H. L., et al. 2021, ApJ, 916, 92, doi: 10.3847/1538-4357/ac096f
  * Wei et al. (2016) Wei, J., Cordier, B., Antier, S., et al. 2016, arXiv e-prints, arXiv:1610.06892.  https://arxiv.org/abs/1610.06892
  * Welsh et al. (2007) Welsh, B. Y., Wheatley, J. M., Seibert, M., et al. 2007, ApJS, 173, 673, doi: 10.1086/516640
  * Yang & Liu (2019) Yang, H., & Liu, J. 2019, ApJS, 241, 29, doi: 10.3847/1538-4365/ab0d28
  * Yang et al. (2017) Yang, H., Liu, J., Gao, Q., et al. 2017, ApJ, 849, 36, doi: 10.3847/1538-4357/aa8ea2
  * Zechmeister & Kürster (2009) Zechmeister, M., & Kürster, M. 2009, A&A, 496, 577, doi: 10.1051/0004-6361:200811296
  * Zimovets et al. (2021) Zimovets, I. V., McLaughlin, J. A., Srivastava, A. K., et al. 2021, Space Sci. Rev., 217, 66, doi: 10.1007/s11214-021-00840-9


# Analysis of Contagion Dynamics with Active Cyber Defenders ††thanks: This
work was supported in part by Colorado State Bill 18-086, and NSF Grants
#2122631 and #2115134. The authors are with the Department of Computer Science
at University of Colorado, Colorado Springs. Contact<EMAIL_ADDRESS>
Keith Paarporn, Shouhuai Xu

###### Abstract

In this paper, we analyze the infection spreading dynamics of malware in a
population of cyber nodes (i.e., computers or devices). Unlike most prior
studies where nodes are reactive to infections, in our setting some nodes are
_active defenders_ meaning that they are able to clean up malware infections
of their neighboring nodes, much like how spreading malware exploits the
network connectivity properties in order to propagate. We formulate these
dynamics as an Active Susceptible-Infected-Susceptible (A-SIS) compartmental
model of contagion. We completely characterize the system’s asymptotic
behavior by establishing conditions for the global asymptotic stability of the
infection-free equilibrium and for an endemic equilibrium state. We show that
the presence of active defenders counter-acts infectious spreading,
effectively increasing the epidemic threshold on parameters for which an
endemic state prevails. Leveraging this characterization, we investigate a
general class of problems for finding optimal investments in active cyber
defense capabilities given limited resources. We show that this class of
problems has unique solutions under mild assumptions. We then analyze an
Active Susceptible-Infected-Recovered (A-SIR) compartmental model, where the
peak infection level of any trajectory is explicitly derived.

##  I Introduction

The spread of computer malware and viruses remains a major cause for concern,
despite the tremendous amount of effort by academia, industry, and government.
This is true despite the substantial progresses in certain areas of
cybersecurity such as cryptography, intrusion detection, firewalls, and anti-
malware tools. These traditional cyber defense approaches are preventive and
reactive in nature because they strive to prevent attacks from succeeding and
react to recognized attacks [1, 2]. However, it is known that cyber attacks
cannot be be completely prevented, for reasons that include undecidability [3]
and human factors [4]. Moreover, reactive defenses are limited because there
may be substantial delays before attacks are detected and cleaned up.

The limitation of traditional defenses is characterized by an asymmetry that
benefits attackers. Namely, the effect of attacks is amplified by the
network’s connectivity (malware spreading), but the effect of preventive and
reactive defenses are not [1, 2, 5, 6, 7]. This asymmetry has led to an
emerging class of countermeasures called active cyber defenses [5, 6, 7, 8,
9], which leverage the same interconnections exploited by attacks to actively
identify and clean up compromised nodes. This is achieved by endowing
uncompromised nodes the ability to “hunt” compromised nodes to clean up their
infection status (or “remotely delivering cures”).

This paper investigates the impact that active defenders have on the spread of
malware. The spreading dynamics of malware draws parallels to the spread of an
infectious disease in a human population, and as such, basic models in
epidemiology are often utilized to study cybersecurity dynamics [10, 11, 2,
12, 13, 14]. The dynamics of these models often follow an epidemic threshold,
such that parameter instances that lie below the threshold characterize an
infection-free equilibrium, and instances above the threshold exhibits an
endemic equilibrium, where a constant fraction is infected over long periods
of time. In this paper, we formulate cybersecurity dynamics as the A-SIS
compartmental model, where nodes are either susceptible to, or infected by,
the malware, and some nodes are active defenders.

There have been studies on characterizing the effectiveness of active
defenders, mainly from a holistic (i.e., network-oriented) perspective [5, 6,
7]. A main focus has been on studying their advantage over preventive and
reactive cyber defenses [5], and their potential side-effects [7]. These
characterization works study mean-field approximations and provide conditions
for the existence or absence of equilibria. A prescription study has derived
optimal control strategies for active cyber defenses in a population contagion
model [6], where it is assumed that every node in the network has active
defense capabilities and no nodes are equipped with reactive defenses. This
motivates us to consider more realistic scenarios, where nodes are equipped
with reactive defense capabilities and some nodes can be equipped with active
defense capabilities. From a practical standpoint in terms of materializing
the potential of active defenses in the real world, ongoing work explores
competent architectures for implementing active defense approaches [9], and
systematizing the challenges that must be tackled before its full potential
can be realized [15].

In relation to the literature on epidemics, our work is similar to the
dynamics of competitive bi-virus models [16, 17, 18], though the mathematical
equations differ in two respects. First, there are only two compartments
(susceptible and infected) in our model of active defenses, whereas bi-virus
models must account for three compartments. Second, active cyber defenses have
inherent asymmetries, since it is possible that only a fraction of the nodes
may implement them. In bi-virus models, any node that is infected with a given
virus type may spread it.

Contributions: Our study abstracts away the underlying complex network
structures originally considered in [5, 7]. Our A-SIS (Active SIS) model is
based on a well-mixed population of nodes, where each node has the same rate
of interaction with others. Under these assumptions, our paper provides a full
characterization of the dynamical properties of the A-SIS contagion model. We
precisely characterize its epidemic threshold, which increases in the fraction
and effectiveness of active defenders (Theorem 3.1). We note that this is in
contrast to many other studies of epidemic models with reactive population
behaviors, i.e. non-pharmaceutical interventions such as social distancing,
where the epidemic threshold remains unchanged from classic non-behavioral
models [19, 20, 21]. Additionally, we fully characterize the global stability
properties of the equilibrium states of the system by identifying suitable
Lyapunov functions (Section III). Specifically, these equilibria are the
infection-free equilibrium (IFE) and the endemic equilibrium states, where we
provide precise infection levels for the latter. Based on these
characterizations, we then consider how a designer should optimize system
security by investing monetary assets in increasing the fraction of active
defense nodes and their effectiveness (Section IV). We show that there is a
unique optimal investment profile, given concave return functions.

##  II The A-SIS contagion model

Our model of active cyber defense is built upon the classic compartmental SIS
model, which we first review below.

###  II-A The SIS Epidemic Model

A malware spreads through a population of nodes, where each node is either
susceptible or infected with the malware.. We denote $s(t)\in[0,1]$ as the
fraction of nodes in the network that are susceptible at time $t$, and
$i(t)\in[0,1]$ as the fraction that are infected. The malware can only be
transmitted from an infected node to a susceptible node upon contact. The per-
contact infection rate is $\beta>0$. Infected nodes are able to independently
recover at the rate $\alpha>0$ by using reactive defenses, e.g. by using
recovery software, intrusion-detection system, or anti-malware tool. The
states $s$ and $i$ evolve according to the following dynamical system:

$\displaystyle\frac{ds}{dt}$ $\displaystyle=-\beta si+\alpha i$ (1)
$\displaystyle\frac{di}{dt}$ $\displaystyle=\beta si-\alpha i$

Under these dynamics, the mass of the population is invariant, and we must
have $s(t)+i(t)=1$ for all times $t$. Therefore, the SIS dynamics may be
reduced to a single state variable,

$\frac{di}{dt}=\beta i(1-i)-\alpha i$ (2)

with initial condition $i(0)\in[0,1]$. The _infection-free equilibrium_ (IFE)
$i_{\text{IFE}}=0$ is an equilibrium of the system. The _endemic_ equilibrium
$i^{*}=1-\frac{\alpha}{\beta}\in(0,1]$ is an equilibrium of the system if and
only if $\frac{\beta}{\alpha}>1$. The solution to this system is well-known.
Its asymptotic properties are summarized.

######  Theorem 2.1 ([22]).

Consider the SIS model (2).

  * •

If $\frac{\beta}{\alpha}\leq 1$, then $i(t)$ converges to $i_{\text{IFE}}$ for
any initial condition $i(0)\in[0,1]$.

  * •

If $\frac{\beta}{\alpha}>1$, then $i(t)$ converges to the _endemic state_
$i^{*}=1-\alpha/\beta$ for any initial condition $i(0)\in(0,1]$.

From the above result, the dynamics of the SIS model follow a threshold on the
parameter $\frac{\beta}{\alpha}$, which is often referred to as the basic
reproduction number.

###  II-B A-SIS: Active cyber defense dynamics

We now formulate our dynamical model of active cyber defense. Like in the SIS
model, every node comes equipped with recovery software (and thus recover from
infection at rate $\alpha$). Now, suppose a fixed fraction $x_{a}\in[0,1]$ of
the nodes are _active defenders_. In addition to reactive defenses, they are
able to employ active defenses against the spreading malware. Upon contact
with any infected node, an active susceptible node is able to clean up the
malware at the infected node with rate $\beta_{a}>0$. We assume that an active
defender can only clean up other infected nodes when it is itself not
infected, which is natural. Thus, a susceptible state is required to implement
active defenses. The remaining fraction $1-x_{a}$ of the nodes are not active
defenders. We refer to these nodes as _reactive_ nodes.

Figure 1: State transition diagram under active cyber defense dynamics
(A-SIS). Each node is one of two types that describe its equipped defense
technology. Active nodes (subscript $a$) have both active and reactive
defenses, whereas reactive nodes (subscript $r$) have only recovery
capability. An infected node can transition to susceptible either through
traditional recovery, or by interactions with active defenders that are
susceptible.

Let $s_{a}(t)$, $s_{r}(t)$, $i_{a}(t)$, and $i_{r}(t)$ be the fraction of
susceptible active, susceptible reactive, infected active, and infected
reactive nodes, respectively. We denote $i(t)\triangleq i_{a}(t)+i_{r}(t)$ as
the total infected fraction at time $t$. The dynamics are given by

$\displaystyle\frac{ds_{a}}{dt}$ $\displaystyle=-\beta
s_{a}i+\beta_{a}s_{a}i_{a}+\alpha i_{a}$ (3) $\displaystyle\frac{di_{a}}{dt}$
$\displaystyle=\beta s_{a}i-\beta_{a}s_{a}i_{a}-\alpha i_{a}$
$\displaystyle\frac{ds_{r}}{dt}$ $\displaystyle=-\beta
s_{r}i+\beta_{a}s_{a}i_{r}+\alpha i_{r}$ $\displaystyle\frac{di_{r}}{dt}$
$\displaystyle=\beta s_{r}i-\beta_{a}s_{a}i_{r}-\alpha i_{r}$

A state transition diagram is shown in Figure 1. From the above equations,
$\frac{ds_{a}}{dt}+\frac{di_{a}}{dt}=0$ and
$\frac{ds_{r}}{dt}+\frac{di_{r}}{dt}=0$, and therefore we have
$s_{a}(t)+i_{a}(t)=x_{a}$ and $s_{r}(t)+i_{r}(t)=1-x_{a}$ for any time $t\geq
0$. The dynamics in (3) is thus a planar system with state
$\boldsymbol{i}\triangleq(i_{a},i_{r})\in[0,x_{a}]\times[0,1-x_{a}]$ governed
by the dynamics

$\displaystyle\frac{di_{a}}{dt}$
$\displaystyle=F_{a}(\boldsymbol{i})\triangleq\beta(x_{a}-i_{a})i-\beta_{a}(x_{a}-i_{a})i_{a}-\alpha
i_{a}$ (A-SIS) $\displaystyle\frac{di_{r}}{dt}$
$\displaystyle=F_{r}(\boldsymbol{i})\triangleq\beta(1-x_{a}-i_{r})i-\beta_{a}(x_{a}-i_{a})i_{r}-\alpha
i_{r}$

We will denote the state space as
$\Gamma\triangleq[0,x_{a}]\times[0,1-x_{a}]$. The initial condition is
specified by
$\boldsymbol{i}_{0}=(i_{a}(0),i_{r}(0))=(i_{a0},i_{r0})\in\Gamma$. We seek to
characterize the equilibria of system (A-SIS) and their stability properties.
We immediately see that the infection-free equilibrium
$\boldsymbol{i}_{\text{IFE}}\triangleq(0,0)$ is an equilibrium point of system
(A-SIS). We say an equilibrium $\boldsymbol{i}^{*}$ is _interior_ if
$\boldsymbol{i}^{*}\in(0,x_{a})\times(0,1-x_{a})$. We will study the stability
properties of A-SIS in the next section.

##  III Stability analysis of A-SIS dynamics

We consider the following stability notions. Let
$\mathcal{E}=\\{\boldsymbol{i}\in\Gamma:F(\boldsymbol{i})=(0,0)\\}$ be the set
of equilibrium points.

######  Definition 1.

An equilibrium point $\boldsymbol{i}^{*}\in\Gamma$ is _globally asymptotically
stable (GAS) with respect to_ $\Gamma$ if for all
$\boldsymbol{i}_{0}\in\Gamma\backslash\mathcal{E}$, $\boldsymbol{i}(t)$
converges to $\boldsymbol{i}^{*}$.

Since we are considering the particular system (A-SIS), we will simply say an
equilibrium point is globally asymptotically stable (GAS). The stability
properties of $\boldsymbol{i}_{\text{IFE}}$ is summarized in our main result
below.

######  Theorem 3.1.

Consider system (A-SIS).

  1. 1.

The equilibrium $\boldsymbol{i}_{\text{IFE}}$ is globally asymptotically
stable if and only if $\frac{\beta}{\alpha}\leq
1+\frac{\beta_{a}x_{a}}{\alpha}$.

  2. 2.

When $\frac{\beta}{\alpha}>1+\frac{\beta_{a}x_{a}}{\alpha}$, there exists a
unique interior equilibrium
$\boldsymbol{i}^{*}=(x_{a}\frac{\lambda_{+}}{\lambda_{+}+\alpha},(1-x_{a})\frac{\lambda_{+}}{\lambda_{+}+\alpha})$
that is globally asymptotically stable, where

$\lambda_{+}\triangleq\beta-\beta_{a}x_{a}-\alpha.$ (4)

Here, $\boldsymbol{i}^{*}$ is referred to as the endemic equilibrium.

Note that Theorem 3.1 degenerates to Theorem 2.1 by setting $x_{a}=0$, meaning
that all nodes only have reactive defenses. The presence of active defenders
increases the threshold for which the IFE is GAS in comparison to the
condition in Theorem 2.1.

###  III-A Global asymptotic stability of the IFE

Before establishing the GES result of $\boldsymbol{i}_{\text{IFE}}$, we first
establish GAS of $\boldsymbol{i}_{\text{IFE}}$ in this subsection. The
Jacobian is

$J(\boldsymbol{i})=\begin{bmatrix}\frac{\partial F_{a}}{\partial
i_{a}}&\frac{\partial F_{a}}{\partial i_{r}}\\\ \frac{\partial F_{r}}{\partial
i_{a}}&\frac{\partial F_{r}}{\partial i_{r}}\end{bmatrix}$ (5)

where

$\displaystyle\frac{\partial F_{a}}{\partial i_{a}}$
$\displaystyle=(\beta-\beta_{a})(x_{a}-2i_{a})-\beta i_{r}-\alpha$ (6)
$\displaystyle\frac{\partial F_{a}}{\partial i_{r}}$
$\displaystyle=\beta(x_{a}-i_{a})$ $\displaystyle\frac{\partial
F_{r}}{\partial i_{a}}$ $\displaystyle=\beta_{a}i_{r}+\beta(1-x_{a}-i_{r})$
$\displaystyle\frac{\partial F_{r}}{\partial i_{r}}$
$\displaystyle=\beta(1-x_{a}-2i_{r}-i_{a})-\beta_{a}(x_{a}-i_{a})-\alpha$

Evaluated at $\boldsymbol{i}_{\text{IFE}}$, we have

$J(\boldsymbol{i}_{\text{IFE}})=\begin{bmatrix}(\beta-\beta_{a})x_{a}-\alpha&\beta
x_{a}\\\ \beta(1-x_{a})&\beta(1-x_{a})-\beta_{a}x_{a}-\alpha\end{bmatrix}$ (7)

The characteristic equation is

$\displaystyle(\lambda-((\beta-\beta_{a})x_{a}-\alpha))(\lambda-(\beta(1-x_{a})-\beta_{a}x_{a}-\alpha))$
(8) $\displaystyle-\beta^{2}x_{a}(1-x_{a})=0$

and the eigenvalues are given by

$\lambda_{+}\triangleq\beta-\beta_{a}x_{a}-\alpha,\quad\lambda_{-}\triangleq-(\beta_{a}x_{a}+\alpha).$
(9)

Since $\lambda_{-}<0$, it is required that $\lambda_{+}<0$ for the IFE to be
locally stable. This is the case under the condition

$x_{a}>\frac{\beta-\alpha}{\beta_{a}}.$ (10)

If $x_{a}<\frac{\beta-\alpha}{\beta_{a}}$, then the IFE is unstable.

Now, let us consider the two nullclines of system (A-SIS),

$\displaystyle\mathcal{I}_{a}$
$\displaystyle\triangleq\left\\{\boldsymbol{i}\in\Gamma:F_{a}(\boldsymbol{i})=0\right\\}$
(11)
$\displaystyle=\left\\{\boldsymbol{i}\in\Gamma:\left(\frac{\alpha}{\beta(x_{a}-i_{a})}-\left(1-\frac{\beta_{a}}{\beta}\right)\right)i_{a}=i_{r}\right\\}$
$\displaystyle\mathcal{I}_{r}$
$\displaystyle\triangleq\left\\{\boldsymbol{i}\in\Gamma:F_{r}(\boldsymbol{i})=0\right\\}$
$\displaystyle=\left\\{\boldsymbol{i}\in\Gamma:i_{a}=\left(\frac{\alpha-\beta(1-x_{a}-i_{r})+\beta_{a}x_{a}}{\beta(1-x_{a}-i_{r})+\beta_{a}i_{r}}\right)i_{r}\right\\}.$

The intersection of the nullclines yields the set of equilibrium points.
Observe that $\boldsymbol{i}_{\text{IFE}}$ is always an equilibrium. We may
define functions

$\displaystyle I_{a}(i_{a})$
$\displaystyle\triangleq\left(\frac{\alpha}{\beta(x_{a}-i_{a})}-\left(1-\frac{\beta_{a}}{\beta}\right)\right)i_{a}$
(12) $\displaystyle I_{r}(i_{r})$
$\displaystyle\triangleq\left(\frac{\alpha-\beta(1-x_{a}-i_{r})+\beta_{a}x_{a}}{\beta(1-x_{a}-i_{r})+\beta_{a}i_{r}}\right)i_{r}$

whose graphs $(i_{a},I_{a}(i_{a}))$ and $(I_{r}(i_{r}),i_{r})$ are the $a$\-
and $r$-nullclines, respectively. The following convexity properties hold.

######  Lemma 3.1.

Function $I_{a}(i_{a})$ for $i_{a}\in[0,x_{a})$ is convex and strictly
increasing in $i_{a}$. Function $I_{r}(i_{r})$ for $i_{r}\in[0,1-x_{a})$ is
convex in $i_{r}$. It is strictly increasing on $i_{r}\in[0,1-x_{a})$ if
$x_{a}\geq\frac{\beta-\alpha}{\beta+\beta_{a}}$, and on
$i_{r}\in[\frac{\beta(1-x_{a})-\beta_{a}x_{a}-\alpha}{\beta},1-x_{a})$ if
$x_{a}<\frac{\beta-\alpha}{\beta+\beta_{a}}$.

Note that $I_{a}(i_{a})$ ($i_{a}\in[0,x_{a}]$) and $I_{r}(i_{r})$
($i_{r}\in[0,1-x_{a}]$) are functions defined on different domains. It will be
more convenient to have them on the same domain, $i_{a}\in[0,x_{a}]$. Such a
representation for the $r$-isocline is given below.

######  Lemma 3.2.

The $r$-nullcline can explicitly be represented as a function of
$i_{a}\in[0,x_{a}]$ with

$\displaystyle\hat{I}_{r}(i_{a})\triangleq$ (13)
$\displaystyle\frac{1}{2}\left[-\left(\frac{d+i_{a}(\beta-\beta_{a})}{\beta}\right)+\right.$
$\displaystyle\quad\quad+\left.\sqrt{\left(\frac{d+i_{a}(\beta-\beta_{a})}{\beta}\right)^{2}+4i_{a}(1-x_{a})}\right]$

where $d\triangleq\alpha+\beta_{a}x_{a}-\beta(1-x_{a})$.

###### Proof.

To obtain this representation, we must solve the equation $I_{r}(i_{r})=i_{a}$
for $i_{r}$. After rearranging terms, it becomes a quadratic equation in
$i_{r}$. Applying the quadratic formula, we obtain (13). ∎

The representation $\hat{I}_{r}(i_{a})$ is the inverse function of
$I_{r}(i_{r})$. Because $I_{r}(i_{r})$ is convex and strictly increasing with
respect to $i_{r}$, it follows that $\hat{I}_{r}(i_{a})$ is concave and
strictly increasing in $i_{a}\in[0,x_{a}]$. These properties allow us to
establish conditions for the existence of a unique interior equilibrium.

######  Lemma 3.3.

If $\lambda_{+}\leq 0$, then $\boldsymbol{i}_{\text{IFE}}$ is the only
isolated equilibrium in $\Gamma$. A unique interior fixed point exists if and
only if $\lambda_{+}>0$.

###### Proof.

We will consider two cases.

When $\lambda_{+}\leq 0$, we have that $I_{a}(0)=\hat{I}_{r}(0)=0$, and can
directly calculate

$\frac{\partial I_{a}}{\partial
i_{a}}=\left(\frac{\alpha}{\beta(x_{a}-i_{a})}-\left(1-\frac{\beta_{a}}{\beta}\right)\right)+i_{a}\frac{\alpha}{\beta(x_{a}-i_{a})^{2}}$
(14)

to obtain

$\frac{\partial I_{a}}{\partial i_{a}}(0)=\frac{\alpha}{\beta
x_{a}}-\left(1-\frac{\beta_{a}}{\beta}\right)\leq\frac{1-x_{a}}{x_{a}}.$ (15)

Similarly, we calculate

$\displaystyle\frac{\partial\hat{I}_{r}}{\partial i_{a}}=$ (16)
$\displaystyle\frac{1}{2}\left[\frac{\beta_{a}}{\beta}-1+\frac{2(\beta-\beta_{a})(d+i_{a}(\beta-\beta_{a}))/\beta^{2}+4(1-x_{a})}{2\sqrt{(d+i_{a}(\beta-\beta_{a}))^{2}/\beta^{2}+4i_{a}(1-x_{a})}}\right]$

and consequently obtain

$\frac{\partial\hat{I}_{r}}{\partial
i_{a}}(0)=\frac{\beta(1-x_{a})}{\alpha+\beta_{a}x_{a}-\beta(1-x_{a})}\geq\frac{1-x_{a}}{x_{a}}.$
(17)

Due to the convexity of $I_{a}$ and concavity of $\hat{I}_{r}$, the only point
at which the nullclines can intersect is the IFE.

When $\lambda_{+}>0$, the system possesses a unique interior equilibrium,
which we can solve for algebraically. We seek the non-zero solution of the
system of equations
$[F_{a}(i_{a},i_{r}),F_{r}(i_{a},i_{r})]^{\top}=[0,0]^{\top}$. We obtain the
unique solution

$i_{a}^{*}=x_{a}\cdot\frac{\lambda_{+}}{\lambda_{+}+\alpha},\quad
i_{r}^{*}=(1-x_{a})\cdot\frac{\lambda_{+}}{\lambda_{+}+\alpha}.$ (18)

∎

Figure 2: Nullclines of system (A-SIS). The arrows depict the directions of
the flow of system (A-SIS). The dashed line is
$i_{r}=\frac{1-x_{a}}{x_{a}}i_{a}$. Here, we have set $\beta=0.3$,
$\beta_{a}=0.35$, $\alpha=0.1$, and $x_{a}=0.6$.

Now, let us consider the candidate Lyapunov function
$V:\Gamma\rightarrow\mathbb{R}_{\geq 0}$ defined by

$V(\boldsymbol{i})\triangleq\max\left\\{\frac{1-x_{a}}{x_{a}}i_{a},i_{r}\right\\}.$
(19)

It holds that $V(\boldsymbol{i})\geq 0$ for all $\boldsymbol{i}$, with
equality if and only if $\boldsymbol{i}=\boldsymbol{i}_{\text{IFE}}$. Observe
that when $x_{a}>\frac{\beta-\alpha}{\beta_{a}}$ ($\lambda_{+}<0$), the line
$\frac{1-x_{a}}{x_{a}}i_{a}$ is a lower bound for $I_{a}(i_{a})$ and an upper
bound for $\hat{I}_{r}(i_{a})$ (see proof of Lemma 3.3). Therefore, when
$\lambda_{+}<0$, we have

$\frac{dV}{dt}=\mathds{1}_{\left\\{i_{r}>\frac{1-x_{a}}{x_{a}}i_{a}\right\\}}F_{r}(\boldsymbol{i})+\mathds{1}_{\left\\{i_{r}\leq\frac{1-x_{a}}{x_{a}}i_{a}\right\\}}F_{a}(\boldsymbol{i})\leq
0$ (20)

with equality if and only if $\boldsymbol{i}=\boldsymbol{i}_{\text{IFE}}$.
Hence, $V(\boldsymbol{i})$ serves as a Lyapunov function that establishes the
global asymptotic stability (w.r.t. $\Gamma$) of
$\boldsymbol{i}_{\text{IFE}}$. This concludes the proof of Theorem 3.1 part 1.

A few remarks regarding the choice of $V$: the function $V(\boldsymbol{i})$ is
of the form of a state max-separable Lyapunov function [23]. Therein,
sufficient conditions on the Jacobian matrix on a forward-invariant convex set
(here, $\Gamma$) are specified for which $V$ serves as a Lyapunov function of
the equilibrium point. Specifically,

######  Fact 3.1 (Corollary 5 from [23]).

Suppose there exists a vector $w>0$ such that $J(\boldsymbol{i})w\leq 0$ for
all $\boldsymbol{i}\in\Gamma$, and $J(\boldsymbol{i}_{\text{IFE}})w<0$. Then

$\max\left\\{\frac{1}{w_{1}}|i_{a}|,\frac{1}{w_{2}}|i_{r}|\right\\}$ (21)

serves as a Lyapunov function and $\boldsymbol{i}_{\text{IFE}}$ is GAS w.r.t
$\Gamma$.

The choice of max-separable Lyapunov function $V$ in (19) is induced from
vector $w=[\frac{x_{a}}{1-x_{a}},1]^{\top}$. However, the sufficient
conditions of Fact 3.1 are not necessarily met. In particular, the second
entry of $J((x_{a},0))w$ is given by $\beta-\beta x_{a}-\alpha$, which can be
positive even when $\lambda_{+}<0$.

###  III-B Global stability of the endemic equilibrium

The system possesses a unique interior equilibrium when
$x_{a}<\frac{\beta-\alpha}{\beta_{a}}$ ($\lambda_{+}>0$) (Lemma 3.3), which is
given by

$i_{a}^{*}=x_{a}\cdot\frac{\lambda_{+}}{\lambda_{+}+\alpha},\quad
i_{r}^{*}=(1-x_{a})\cdot\frac{\lambda_{+}}{\lambda_{+}+\alpha}.$ (22)

We will refer to this interior equilibrium as the _endemic_ equilibrium,
$\boldsymbol{i}^{*}=(i_{a}^{*},i_{r}^{*})$. To establish global asymptotic
stability (part 2 of Theorem 3.1), we will consider the candidate Lyapunov
function $V_{R}:\Gamma\rightarrow\mathbb{R}_{\geq 0}$,

$V_{R}(\boldsymbol{i})\triangleq\max\left\\{|i_{a}-x_{a}f|,R\cdot|i_{r}-(1-x_{a})f|\right\\}$
(23)

for some $R>0$, where
$f\triangleq\frac{\lambda_{+}}{\lambda_{+}+\alpha}\in(0,1)$. We can write it
more explicitly as

$V_{R}(\boldsymbol{i})=\begin{cases}x_{a}f-i_{a},&\text{if
}\boldsymbol{i}\in\Gamma_{a}^{<}\\\ i_{a}-x_{a}f,&\text{if
}\boldsymbol{i}\in\Gamma_{a}^{\geq}\\\ R((1-x_{a})f-i_{r}),&\text{if
}\boldsymbol{i}\in\Gamma_{r}^{<}\\\ R(i_{r}-(1-x_{a})f),&\text{if
}\boldsymbol{i}\in\Gamma_{r}^{\geq}\\\ \end{cases}$ (24)

where the regions are defined as

$\displaystyle\Gamma_{a}^{<}$
$\displaystyle\triangleq\left\\{\boldsymbol{i}:V_{R}(\boldsymbol{i})=|i_{a}-x_{a}f|,\
i_{a}-x_{a}f<0\right\\}$ (25) $\displaystyle\Gamma_{a}^{\geq}$
$\displaystyle\triangleq\left\\{\boldsymbol{i}:V_{R}(\boldsymbol{i})=|i_{a}-x_{a}f|,\
i_{a}-x_{a}f\geq 0\right\\}$ $\displaystyle\Gamma_{r}^{<}$
$\displaystyle\triangleq\left\\{\boldsymbol{i}:V_{R}(\boldsymbol{i})=R|i_{r}-(1-x_{a})f|,i_{r}-(1-x_{a})f<0\right\\}$
$\displaystyle\Gamma_{r}^{\geq}$
$\displaystyle\triangleq\left\\{\boldsymbol{i}:V_{R}(\boldsymbol{i})=R|i_{r}-(1-x_{a})f|,i_{r}-(1-x_{a})f\geq
0\right\\}$

It holds that $V_{R}(\boldsymbol{i})\geq 0$ for all $\boldsymbol{i}\in\Gamma$,
and equality is satisfied if and only if $\boldsymbol{i}=\boldsymbol{i}^{*}$.
An illustration of the regions is shown in Figure 3.

Figure 3:  The regions defined in the Lyapunov function $V_{R}$ (24). We set
$\beta=0.3$, $\beta_{a}=0.28$, $\alpha=0.1$, $x_{a}=0.2$, which is in the
regime $x_{a}\leq\frac{\beta-\alpha}{\beta+\beta_{a}}$. Here we set $R=0.5$,
which satisfies the condition of (26), $0.25\leq R<\min\\{0.8746,0.6143\\}$.

In the case $x_{a}\leq\frac{\beta-\alpha}{\beta+\beta_{a}}$, we will select
any $R$ in the range

$\frac{x_{a}}{1-x_{a}}\leq
R<\min\left\\{\frac{1}{\hat{I}^{\prime}_{r}(i_{a}^{*})},\frac{\beta
x_{a}f}{d+\beta f(1-x_{a})}\right\\}.$ (26)

The condition $R<1/\hat{I}^{\prime}_{r}(i_{a}^{*})$ ensures that the graph of
$\hat{I}_{r}$, for $i_{a}\geq x_{a}f$, is contained in $\Gamma_{a}^{\geq}$.
The condition $R<\frac{\beta x_{a}f}{d+\beta f(1-x_{a})}$ ensures that the
graph of $\hat{I}_{r}$, for $i_{a}<x_{a}f$, is contained in $\Gamma_{a}^{<}$.
The condition $\frac{x_{a}}{1-x_{a}}\leq R$ ensures that the graph of $I_{a}$
in $\Gamma$ is contained only in either $\Gamma_{r}^{<}$ (for $i_{a}<x_{a}f$)
or $\Gamma_{r}^{\geq}$ (for $i_{a}\geq x_{a}f$). Under (26), the following
properties hold:

  * •

Any $\boldsymbol{i}\in\Gamma_{a}^{<}$ satisfies $F_{a}(\boldsymbol{i})>0$.

  * •

Any $\boldsymbol{i}\in\Gamma_{a}^{\geq}$ satisfies $F_{a}(\boldsymbol{i})\leq
0$ with equality if and only if $i_{a}=x_{a}f$.

  * •

Any $\boldsymbol{i}\in\Gamma_{r}^{<}$ satisfies $F_{r}(\boldsymbol{i})>0$.

  * •

Any $\boldsymbol{i}\in\Gamma_{r}^{\geq}$ $F_{r}(\boldsymbol{i})\leq 0$ with
equality if and only if $i_{r}=(1-x_{a})f$.

We thus obtain

$\frac{dV_{R}}{dt}(\boldsymbol{i})=\begin{cases}-\frac{di_{a}}{dt},&\text{if
}\boldsymbol{i}\in\Gamma_{a}^{<}\\\ \frac{di_{a}}{dt},&\text{if
}\boldsymbol{i}\in\Gamma_{a}^{\geq}\\\ -R\frac{di_{r}}{dt},&\text{if
}\boldsymbol{i}\in\Gamma_{r}^{<}\\\ R\frac{di_{r}}{dt},&\text{if
}\boldsymbol{i}\in\Gamma_{r}^{\geq}\\\ \end{cases}\ \ \leq 0,$ (27)

with equality if and only if $\boldsymbol{i}=\boldsymbol{i}^{*}$. Similar
arguments can be applied in the case
$x_{a}>\frac{\beta-\alpha}{\beta+\beta_{a}}$. In this case, the arguments hold
for the choice $R=1$. This establishes global asymptotic stability (w.r.t.
$\Gamma$) of $\boldsymbol{i}^{*}$ , which concludes the proof of Theorem 3.1
part 2.

##  IV Optimal investments in active defense

We have now fully characterized the global asymptotic behavior of system
A-SIS. It may be summarized by the limiting infected fraction

$L(x_{a},\beta_{a})\triangleq\lim_{t\rightarrow\infty}i(t)=\begin{cases}1-\frac{\alpha}{\beta-\beta_{a}x_{a}},&\text{if
}\beta_{a}x_{a}<\beta-\alpha\\\ 0,&\text{else}\end{cases}.$ (28)

In this section, we consider a system operator that makes investment decisions
to promote the active defense capabilities of the network. Suppose the
operator has a limited monetary budget $M>0$. It decides to invest an amount
of money $a\geq 0$ in increasing the total fraction $x_{a}$ of active
defenders, with a return function $h:\mathbb{R}_{\geq 0}\rightarrow[0,1]$ that
is increasing. This reflects a plausible scenario since active defenses are
new tools and capabilities which would incur extra costs to install on network
nodes. Likewise, it decides to invest an amount $b\geq 0$ in increasing the
effectiveness of active defenders, with an expected return function
$g:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$. This reflects the costs
associated with improving active defense tactics, where more advanced tactics
incur higher costs (e.g., requiring the active defender to collect and process
more data from its neighboring node it is trying to help out). The
optimization problem that the operator faces is thus formulated as

$\displaystyle\min_{y=(a,b)}$ $\displaystyle L(h(a),g(b))$ (29) s.t.
$\displaystyle a,b\geq 0$ $\displaystyle a+b\leq M$

This problem becomes trivial if there is a feasible pair $(a,b)$ that
satisfies $g(b)h(a)\geq\beta-\alpha$. In this case, the infection can be
eradicated. As such, we will consider the cases where no feasible pair
achieves this, i.e. $g(b)h(a)<\beta-\alpha$ for all $a,b$ with $a+b\leq M$.

We will proceed by defining the following structural properties for the return
functions.

######  Definition 2.

We denote the family of functions $\mathcal{D}$ as the set of single-variable
functions $f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ that are
strictly increasing, twice continuously differentiable, concave, and satisfies
$f(0)=0$.

For the formulation of optimization problem (29), we place the following
assumptions on the return functions $h,g$.

######  Assumption 1.

The function $g\in\mathcal{D}$. The function $h(a)$ is of the form
$h(a)=\min\\{\hat{h}(a),1\\}$, where $\hat{h}\in\mathcal{D}$.

Concavity is a common assumption that describes marginal diminishing returns
on investment. For the function $h(a)$, there is a value $t>0$ for which
monetary investments larger than $t$ will convert the entire population to
become active defenders. It can be the case that $t=\infty$, in which case
$h\in\mathcal{D}$. The assumption $h(0)=g(0)=0$ asserts that zero investment
yields zero returns. The following result establishes that there exists a
unique optimal investment that solves (29).

######  Theorem 4.1.

Suppose $g,h$ satisfy the properties of Assumption 1. Suppose $t\geq M$. Then
(29) has a unique solution $y^{*}=(a^{*},b^{*})$, where $a^{*}\in(0,M)$
satisfies

$g(M-a^{*})h^{\prime}(a^{*})=g^{\prime}(M-a^{*})h(a^{*})$ (30)

and $b^{*}=M-a^{*}$. Suppose $t<M$. If $g^{\prime}(M-t)\geq
g(M-t)\hat{h}^{\prime}(t)$, then the unique solution is given by the same
$y^{*}$. If $g^{\prime}(M-t)<g(M-t)\hat{h}^{\prime}(t)$, then the unique
solution is given by $a^{*}=t$, $b^{*}=M-t$.

###### Proof.

First, observe that an investment profile with $a=0$ and $b>0$, or $a>0$ and
$b=0$ cannot be optimal. Thus, an optimal investment must satisfy $a,b>0$. By
complementary slackness, the two multipliers associated with the non-
negativity constraints on $a,b$ must be zero.

Let $\lambda$ be the multiplier associated with the inequality constraint,
$a+b\leq M$. Note that if $\lambda=0$, the first-order conditions become
$g(b)=0$ and $h(a)=0$, which has the unique solution $a=b=0$. However, this
cannot be an optimal solution. Thus, we suppose $\lambda>0$. Here, the budget
must be met, i.e. $a+b=M$. We obtain the first-order condition

$H_{1}(a)=H_{2}(a)$ (31)

where $H_{1}(a)=g(M-a)h^{\prime}(a)$ and $H_{2}(a)=g^{\prime}(M-a)h(a)$. To
see this, we must have

$\displaystyle\frac{\alpha
g(M-a)h^{\prime}(a)}{(\beta-g(M-a)h(a))^{2}}=\lambda=\frac{\alpha
h(a)g^{\prime}(M-a)}{(\beta-g(M-a)h(a))^{2}}$ (32)

Since we are considering the cases where $\beta-g(b)h(a)>\alpha>0$, the
denominator may be eliminated.

Case 1:  $M\leq t$. For $a\in(0,M)$, $H_{1}(a)$ is strictly decreasing because

$H_{1}^{\prime}(a)=-g^{\prime}(M-a)h^{\prime}(a)+g(M-a)h^{\prime\prime}(a)<0,$
(33)

which follows from the assumptions that $h$ and $g$ are strictly increasing,
concave, and twice differentiable (Assumption 1). For $a\in(0,M)$, $H_{2}(a)$
is strictly increasing because

$H_{2}^{\prime}(a)=-g^{\prime\prime}(M-a)h(a)+g^{\prime}(M-a)h^{\prime}(a)>0,$
(34)

which follows similarly. Moreover, $H_{1}(0)>0$, $H_{1}(M)=0$, and
$H_{2}(0)=0$, $H_{2}(M)>0$. By the intermediate value theorem and by strict
monotonicity of $H_{1}$ and $H_{2}$, there exists a unique solution $a^{*}$ to
(31).

Because Slater’s condition holds for (29), the KKT conditions are necessary
and sufficient for optimality. Taking $b^{*}=M-a^{*}$ and $\lambda^{*}$ in
(32), we have showed that $(a^{*},b^{*},\lambda^{*})$ uniquely satisfy the KKT
conditions.

Case 2:  $M>t$. In this case, no optimal solution will allocate $a>t$, since
any excess allocation here may be invested in $b$. Let us re-formulate (29)
with the additional constraint $a\leq t$, and denote $\lambda_{a}\geq 0$ as
its associated multiplier. If $g^{\prime}(M-t)\geq g(M-t)\hat{h}^{\prime}(t)$,
a unique solution $a^{*}\in(0,t]$ satisfies (32), which is the same solution
as Case 1. Now suppose $g^{\prime}(M-t)<g(M-t)\hat{h}^{\prime}(t)$. Here, note
that no solution $a\in(0,t)$ to (32) exists. Thus, considering $\lambda_{a}>0$
($a=t$), the first-order condition now becomes

$\displaystyle\alpha g(M-t)\partial h(t)$ $\displaystyle=\alpha
g^{\prime}(M-t)$ (35) $\displaystyle\quad+\lambda_{a}(\beta-g(M-t))^{2},$

where $\partial h(t)\in[0,\hat{h}^{\prime}(t)]$ is any sub-derivative of $h$
at $a=t$, and we used the fact that $h(t)=1$. Taking any $\partial h(t)$ such
that $g(M-t)\partial h(t)-g^{\prime}(M-t)>0$ (possible by assumption), we
obtain

$\lambda_{a}^{*}=\frac{\alpha(g(M-t)\partial
h(t)-g^{\prime}(M-t))}{(\beta-g(M-t))^{2}}>0.$ (36)

Lastly, we recover $\lambda^{*}=\frac{\alpha
h(t)g^{\prime}(M-t)}{(\beta-g(M-t))^{2}}$. Thus, $a^{*}=t$, $b^{*}=M-t$,
$\lambda^{*}$, and $\lambda_{a}^{*}$ satisfy the KKT conditions, and thus
$a^{*},b^{*}$ are solutions of (29). ∎

######  Example 1.

For linear returns on investment, $h(a)=\min\\{c_{1}a,1\\}$ and $g(b)=c_{2}b$
for constants $c_{1},c_{2}>0$. From Theorem 4.1, if $1/c_{1}>M$, we have
$a^{*}=b^{*}=M/2$. If $M/2\leq 1/c_{1}<M$, we also obtain $a^{*}=b^{*}=M/2$.
If $1/c_{1}<M/2$, then $a^{*}=1/c_{1}$ and $b^{*}=M-1/c_{1}$.

######  Example 2.

Suppose $h(a)=\frac{a}{a+c_{1}}$ and $g(b)=\bar{\beta}\frac{b}{b+c_{2}}$ for
constants $c_{1},c_{2},\bar{\beta}>0$. From (30), we obtain
$a^{*}=\frac{c_{1}(M+c_{2})}{c_{1}-c_{2}}\left[1-\sqrt{1-\frac{(c_{1}-c_{2})M}{c_{1}(M+c_{2})}}\right]<M$
if $c_{1}\neq c_{2}$, and $a^{*}=M/2$ if $c_{1}=c_{2}$.

##  V A-SIR dynamics of active cyber defense

In this section, we investigate the impact of active defenders in the SIR
(susceptible-infected-recovered) epidemics model. Here, a node that has been
cleared of infectious malware obtains permanent protection against any future
infection. The protection can be conferred either through reactive defenses
(with rate $\alpha$), or through active defenses (with rate $\beta_{a}$). As
such, we keep track of the five states $s_{a}(t)$, $s_{r}(t)$, $i_{a}(t)$,
$i_{r}(t)$, and $r(t)$. Note that we need not differentiate between active and
reactive protected nodes, since they are effectively removed from any further
interactions.

$\displaystyle\frac{ds_{a}}{dt}$ $\displaystyle=-\beta\cdot s_{a}i$ (A-SIR)
$\displaystyle\frac{ds_{r}}{dt}$ $\displaystyle=-\beta\cdot s_{r}i$
$\displaystyle\frac{di_{a}}{dt}$ $\displaystyle=\underbrace{\beta\cdot
s_{a}i}_{\text{malware infection}}-\underbrace{\beta_{a}\cdot
s_{a}i_{a}}_{\text{active defense}}-\underbrace{\alpha i_{a}}_{\text{reactive
defense}}$ $\displaystyle\frac{di_{r}}{dt}$ $\displaystyle=\beta\cdot
s_{r}i-\beta_{a}\cdot s_{a}i_{r}-\alpha i_{r}$ $\displaystyle\frac{dr}{dt}$
$\displaystyle=\beta_{a}\cdot s_{a}i+\alpha i$

with initial conditions $(s_{a0},s_{r0},i_{a0},i_{r0})\in[0,1]^{4}$ that
satisfy $s_{a0}+s_{r0}+i_{a0}+i_{r0}=1$. Here, we are assuming that no node is
initially fully protected from the malware, meaning $r(0)=0$. We consider the
class of initial value problems with the above dynamics (A-SIR) parameterized
by a fixed fraction of initially infected nodes $i_{0}$ and the fraction of
active defenders in the population, namely $s_{a0}$. Note that since no node
is initially fully protected, we have $s_{0}=s_{a0}+s_{r0}=1-i_{0}$. Also,
observe that the roles of infected active or infected reactive nodes are
indistinguishable (both types infect susceptibles at the same rate, and both
attain protection at the same rates). Indeed, the total infected fraction $i$
depends only on $i$, but not on $(i_{a},i_{r})$:

$\frac{di}{dt}=\beta\cdot si-\beta_{a}\cdot s_{a}i-\alpha i.$ (37)

Therefore, we only consider the initial fraction of active susceptible nodes,
namely $s_{a0}$.

The following Theorem characterizes the peak infection level for any initial
value problem of the A-SIP dynamics.

######  Theorem 5.1.

Consider any initial value problem of the A-SIP dynamics, and denote by
$i(t)$, $t\geq 0$ the resulting state trajectory for the total infected
fraction of nodes. Then $i_{\text{pk}}\triangleq\max_{t\geq 0}i(t)$ is
characterized by

$i_{\text{pk}}=\begin{cases}1-\frac{\alpha}{\beta}-\frac{\beta_{a}}{\beta}s_{a0}+\frac{\alpha}{\beta}\log\frac{\alpha}{\beta
s_{0}-\beta_{a}s_{a0}},&\text{if }s_{a0}<\frac{\beta
s_{0}-\alpha}{\beta_{a}}\\\ i_{0},&\text{if }s_{a0}\geq\frac{\beta
s_{0}-\alpha}{\beta_{a}}\end{cases}.$ (38)

###### Proof.

We can characterize the trajectory of $i$ as a function of $s_{a}$ as follows.
Observe that

$\frac{ds_{a}}{ds_{r}}=\frac{s_{a}}{s_{r}}.$ (39)

Integrating this equation, we obtain the relation

$s_{a}(s_{r})=\frac{s_{a}(s_{r0})}{s_{r0}}\cdot
s_{r}=\frac{s_{a0}}{s_{0}-s_{a0}}\cdot s_{r},$ (40)

where we denote $s_{0}=s_{a0}+s_{r0}$. Using this relation, we may write

$\frac{di}{dt}=\left(\beta\frac{s_{0}}{s_{a0}}-\beta_{a}\right)s_{a}i-\alpha
i,$ (41)

and subsequently,

$\frac{di}{ds_{a}}=-\frac{A}{\beta}+\frac{\alpha}{\beta s_{a}},$ (42)

where $A:=\beta\frac{s_{0}}{s_{a0}}-\beta_{a}$. Observe that function
$i(s_{a})$ is concave in $s_{a}\in(0,\infty)$. The peak of the trajectory
$i(s_{a})$ is obtained by setting the above equation to $0$, and solving for
$s_{a}$.

In the case $A\leq 0$, or equivalently $s_{a0}\geq\frac{\beta
s_{0}}{\beta_{a}}$, function $i(s_{a})$ does not have a peak for any
$s_{a}\geq 0$. Therefore, the infected fraction $i(t)$ is monotonically
decreasing in time until eradication, and hence $\max_{t\geq 0}i(t)=i_{0}$.

In the case $A>0$, function $i(s_{a})$ peaks precisely at
$s_{a}^{*}=\frac{\alpha}{A}$. Since it must hold that $s_{a}\in[0,s_{a0})$
throughout the entire trajectory, the infected fraction $i(t)$ peaks after the
initial time if and only if $\frac{\alpha}{A}<s_{a0}$. This is equivalent to
the condition $s_{a0}<\frac{\beta s_{0}-\alpha}{\beta_{a}}$. To determine the
peak infection level, we integrate (42) to obtain

$i(s_{a})=i_{0}-\frac{A}{\beta}(s_{a}-s_{a0})+\frac{\alpha}{\beta}\log\frac{s_{a}}{s_{a0}}.$
(43)

Evaluating at $s_{a}^{*}=\frac{\alpha}{A}$, the peak value is

$i^{*}=1-\frac{\alpha}{\beta}-\frac{\beta_{a}}{\beta}s_{a0}+\frac{\alpha}{\beta}\log\frac{\alpha}{\beta
s_{0}-\beta_{a}s_{a0}}$ (44)

where we have used the fact that $s_{0}+i_{0}=1$. Lastly, if
$\frac{\alpha}{A}\geq s_{a0}$, or equivalently $s_{a0}\geq\frac{\beta
s_{0}-\alpha}{\beta_{a}}$, then the infected fraction $i(t)$ is monotonically
decreasing, and hence $i^{*}=i_{0}$. ∎

The above result indicates that the infection level will not exceed
$i_{\text{pk}}$ for any time $t\geq 0$. Thus, if the objective of a system
operator is to ensure the network never reaches an infectivity level above a
certain desired threshold $\tau$, then equation (38) can help specify design
parameters (e.g. $\beta_{a}$, $s_{a0}$, $\alpha$) on defense that meet this
requirement. A precise characterization will be left for future work.

##  VI Conclusion

Active cyber defense is an emerging technology. We have proposed a novel
active cyber defense model based on the epidemiological SIS population
dynamics. We fully characterized the behavior of the dynamics, establishing
global asymptotic stability of infection-free and endemic fixed points. We
show that deploying active cyber defenses has an impact on the epidemic
threshold, unlike other mitigation approaches studied in epidemic models such
as reactive social distancing. We further leverage the characterization to
determine optimal investments in active cyber defense. As a side-product, we
also characterize the effect of deploying active cyber defense in an SIR
model. We hope this study will inspire more investigations on the
effectiveness of active cyber defense, which is a new paradigm in cyber
defense that could be a game-changer in cybersecurity.

## References

  * [1] S. Xu, W. Lu, L. Xu, and Z. Zhan, “Adaptive epidemic dynamics in networks: Thresholds and control,” _ACM Transactions on Autonomous and Adaptive Systems (TAAS)_ , vol. 8, no. 4, pp. 1–19, 2014.
  * [2] R. Zheng, W. Lu, and S. Xu, “Preventive and reactive cyber defense dynamics is globally stable,” _IEEE Transactions on Network Science and Engineering_ , vol. 5, no. 2, pp. 156–170, 2017.
  * [3] L. M. Adleman, “An abstract theory of computer viruses,” in _Advances in Cryptology—CRYPTO’88: Proceedings 8_. Springer, 1990, pp. 354–374.
  * [4] R. Montañez, E. Golob, and S. Xu, “Human cognition through the lens of social engineering cyberattacks,” _Frontiers in psychology_ , vol. 11, p. 1755, 2020.
  * [5] S. Xu, W. Lu, and H. Li, “A stochastic model of active cyber defense dynamics,” _Internet Mathematics_ , vol. 11, no. 1, pp. 23–61, 2015.
  * [6] W. Lu, S. Xu, and X. Yi, “Optimizing active cyber defense,” in _Decision and Game Theory for Security: 4th International Conference, GameSec 2013, Fort Worth, TX, USA, November 11-12, 2013. Proceedings 4_. Springer, 2013, pp. 206–225.
  * [7] R. Zheng, W. Lu, and S. Xu, “Active cyber defense dynamics exhibiting rich phenomena,” in _Proceedings of the 2015 Symposium and Bootcamp on the Science of Security_ , 2015, pp. 1–12.
  * [8] P. Théron and A. Kott, “When autonomous intelligent goodware will fight autonomous intelligent malware: A possible future of cyber defense,” in _MILCOM 2019-2019 IEEE Military Communications Conference (MILCOM)_. IEEE, 2019, pp. 1–7.
  * [9] P. Theron, A. Kott, M. Drašar, K. Rzadca, B. LeBlanc, M. Pihelgas, L. Mancini, and F. De Gaspari, “Reference architecture of an autonomous agent for cyber defense of complex military systems,” _Adaptive Autonomous Secure Cyber Systems_ , pp. 1–21, 2020.
  * [10] A. Ganesh, L. Massoulié, and D. Towsley, “The effect of network topology on the spread of epidemics,” in _Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies._ , vol. 2. IEEE, 2005, pp. 1455–1466.
  * [11] P. Van Mieghem, J. Omic, and R. Kooij, “Virus spread in networks,” _IEEE/ACM Transactions On Networking_ , vol. 17, no. 1, pp. 1–14, 2008.
  * [12] Y. Han, W. Lu, and S. Xu, “Preventive and reactive cyber defense dynamics with ergodic time-dependent parameters is globally attractive,” _IEEE Transactions on Network Science and Engineering_ , vol. 8, no. 3, pp. 2517–2532, 2021.
  * [13] V. S. Varma, Y. Hayel, and I.-C. Morărescu, “A non-cooperative resource utilization game between two competing malware,” _IEEE Control Systems Letters_ , vol. 7, pp. 67–72, 2022.
  * [14] V. S. Mai, R. J. La, and A. Battou, “Optimal cybersecurity investments using sis model: Weakly connected networks,” in _GLOBECOM 2022-2022 IEEE Global Communications Conference_. IEEE, 2022, pp. 6097–6102.
  * [15] S. Xu, “Aica development challenges,” in _Building an Artificial Intelligence Cyber-Defense Agent_ , A. Kott, Ed. Springer, 2022, vol. 74, pp. 1–31.
  * [16] J. Liu, P. E. Paré, A. Nedić, C. Y. Tang, C. L. Beck, and T. Başar, “Analysis and control of a continuous-time bi-virus model,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 12, pp. 4891–4906, 2019.
  * [17] A. Santos, J. M. Moura, and J. M. Xavier, “Bi-virus sis epidemics over networks: Qualitative analysis,” _IEEE Transactions on Network Science and Engineering_ , vol. 2, no. 1, pp. 17–29, 2015.
  * [18] V. Doshi, J. Hu, and D. Y. Eun, “Bi-sis epidemics on graphs - quantitative analysis of coexistence equilibria,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_ , 2022, pp. 5608–5613.
  * [19] K. Paarporn, C. Eksin, J. S. Weitz, and J. S. Shamma, “Networked sis epidemics with awareness,” _IEEE Transactions on Computational Social Systems_ , vol. 4, no. 3, pp. 93–103, 2017.
  * [20] C. Eksin, K. Paarporn, and J. S. Weitz, “Systematic biases in disease forecasting–the role of behavior change,” _Epidemics_ , vol. 27, pp. 96–105, 2019.
  * [21] T. C. Reluga, “Game theory of social distancing in response to an epidemic,” _PLoS computational biology_ , vol. 6, no. 5, p. e1000793, 2010.
  * [22] W. Mei, S. Mohagheghi, S. Zampieri, and F. Bullo, “On the dynamics of deterministic epidemic propagation over networks,” _Annual Reviews in Control_ , vol. 44, pp. 116–128, 2017.
  * [23] S. Coogan, “A contractive approach to separable lyapunov functions for monotone systems,” _Automatica_ , vol. 106, pp. 349–357, 2019.


$f_{4}$ | Inter Down | $e_{2}\times s_{0}^{2}-\lvert\\{x\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\mid x\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\in\mathsf{S}\\}\rvert$
$f_{5}$ | Diff Up | $e_{2}\times s_{0}^{2}-\lvert\\{x\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\mid x\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\in\mathsf{S}\\}\rvert$
$f_{6}$ | Diff Down | $e_{2}\times s_{0}^{2}-\lvert\\{x\not\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\mid x\not\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\in\mathsf{S}\\}\rvert$
$f_{7}$ | Single Up | $s_{0}-\lvert\\{x\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}[x]\mid x\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}[x]\in\mathsf{S}\\}\rvert$
$f_{8}$ | Single Down | $e_{2}\times s_{0}-\lvert\\{x\approx y\mid x\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}[y]\in\mathsf{S}\\}\rvert$
$f_{9}$ | Set Diseq | $s_{0}^{2}-\lvert\\{\langle z_{s,t}\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s,z_{s,t}\not\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}t\rangle\mid s\not\approx t\in\mathsf{S}^{*}\\}\rvert$
$f_{10}$ | Prod Up | $e_{2}^{2}\times s_{0}^{2}-\lvert\\{\langle\bar{x},\bar{y}\rangle\mid\langle\bar{x},\bar{y}\rangle\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\otimes t\in\mathsf{S}\\}\rvert$
$f_{11}$ | Prod Down | $e_{2}^{2}\times s_{0}^{2}-\lvert\\{\langle\bar{x},\bar{y}\rangle\mid\bar{x}\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\in\mathsf{S},\bar{y}\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}t\in\mathsf{S}\\}\rvert$
$f_{12}$ | Join Up | $e_{2}^{2}\times s_{0}^{2}-\lvert\\{\langle\bar{x},\bar{y}\rangle\mid\langle\bar{x},\bar{y}\rangle\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\otimes t\in\mathsf{S}\\}\rvert$
$f_{13}$ | Join Down | $e_{2}^{2}\times s_{0}^{2}-\lvert\\{\langle\bar{x},\bar{y}\rangle\mid\bar{x}\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\in\mathsf{S},\bar{y}\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}t\in\mathsf{S}\\}\rvert$
$f_{14}$ | Filter Up | $\begin{array}[]{ll}e_{2}\times s_{0}&-\lvert\\{\langle p(e),e\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}\sigma(p,s)\rangle\mid p(e)\in\mathsf{E},e\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}\sigma(p,s)\in\mathsf{S}\\}\rvert\\\ &-\lvert\\{\langle\neg p(e),e\not\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}\sigma(p,s)\rangle\mid\neg p(e)\in\mathsf{E},e\not\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}\sigma(p,s)\in\mathsf{S}\\}\rvert\end{array}$
$f_{15}$ | Filter Down | $e_{2}\times s_{0}-\lvert\\{\langle p(e),e\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\rangle\mid p(e)\in\mathsf{E},e\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s\in\mathsf{S}\\}\rvert$
Figure 14: Ranking functions for relation rules.

Each application of any rule would only reduce its corresponding function and
leave the rest functions unchanged. In other words,
$f_{i}(c^{\prime})=f_{i}(c)-1$, and $f_{j}(c^{\prime})=f_{j}(c)$ for
$i,j\in[1,15],i\neq j$. It is clear that $c\succ c^{\prime}$. This means the
derivation tree is finite, and therefore the calculus with the above
assumptions is terminating. ∎

See 0.3.1

###### Proof.

Note that the graph $G$ does not change in all configurations since the
calculus rules do not introduce new set terms, or new edges. We cut the graph
$G$ into two subgraphs $G_{1},G_{2}$ such that subgraph $G_{1}$ includes all
cycles in $G$ and all map terms are in subgraph $G_{2}$. Without loss of
generality, we assume all edges in the cut set are only connected to map terms
in $G_{2}$. Otherwise, we would have a black edge $(u,v)$ such that $v\in
V(G_{2})$ is not a map term, and it can be safely added to $G_{1}$ because $v$
is not in any cycle. From Lemma .8.1 the calculus is terminating in $G_{1}$.
Suppose the number of element terms in $G_{1}$ after termination is $e_{1}$.
We show the calculus is terminating in $G_{2}$ when it has no cycles. Suppose
$G_{2}$ has $e_{2}$ element terms, and $s_{2}$ set terms. In the worst case,
in the sense of fresh variables, assume all these $s_{2}$ terms are map terms
$m_{i}$ where $i\in[1,s_{2}]$ such that $m_{i}=\pi(f_{i},m_{i-1}),i>1$.
Applying rules Map Up and Map Down would introduce at most $e_{2}\times s_{2}$
new element terms. Define $e^{\prime}_{2}=e_{1}+e_{2}\times s_{2}$. Both rules
Map Up and Map Down could be applied at most $e^{\prime}_{2}$ times, and the
ranking functions would be
$e^{\prime}_{2}-\lvert\\{f(e)\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}\pi(f,s)\mid
e\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s,\pi(f,s)\in\mathcal{T}(\mathsf{S})\\}\rvert$
and
$e^{\prime}_{2}-\lvert\\{\langle\varphi_{1},\varphi_{2}\rangle\mid\varphi_{1}=f(w)\approx
e,\varphi_{2}=w\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}s,\varphi_{1}\in\mathsf{E},\varphi_{2}\in\mathsf{S},e\mathrel{\vphantom{\sqsubset}\text{\ooalign{$\sqsubset$\cr$-$\cr}}}\pi(f,s)\in\mathsf{S}^{*}\\}\rvert$
respectively. Therefore, the calculus is terminating in $G_{2}$. The calculus
is still terminating if there are non-map terms in $G_{2}$, since the ranking
functions would be similar to the ones in Figure 14 after accounting for the
new terms introduced by map terms.

Since both subgraphs $G_{1},G_{2}$ are terminating separately, we turn our
attention to edges in the cut set. First, the $e_{2}^{\prime}$ elements in
$G_{2}$ could be propagated to $G_{1}$ with edges of any label in
$\\{=,\sqcup,\sqcap,\setminus,\otimes,\sigma,\pi\\}$. $G_{1}$ would still be
terminating with the additional $e^{\prime}_{2}$ elements. Suppose the number
of elements in $G_{1}$ after termination is $e^{\prime}_{1}$. These
$e^{\prime}_{1}$ elements could be propagated back and forth through the edges
in the cut set. However, this process is only repeated once for each edge in
the cut set which is finite. After that, all elements would have been
propagated in both $G_{1}$ and $G_{2}$. Now both subgraphs are terminating
separately which concludes the proof. ∎

##  .9 Examples of SQL Translation

Figure 15 shows how the theory of tables and theory of nullables are used to
translate many SQL queries. Exampele .9.1 shows how to translate one of
calcite’s benchmarks into these theories.

SQL | SMT
---|---
int, varchar | $\mathsf{Nullable}(\mathsf{Int}),\mathsf{Nullable}(\mathsf{String})$
select * from (values (’a’),(’a’)) | $\mathsf{bag}(\langle"a"\rangle,2)$
is null, is not null | $\mathsf{isNull},\mathsf{isSome}$
select column1 + 1 from s | $\pi(\lambda t.\mathsf{lift}(+,\mathsf{select}_{0}(t),\mathsf{some}(1)),s)$
select * from s where column1 $>$ 5 | $\sigma(\lambda t.\mathsf{isSome}(\mathsf{select}_{0}(t))\wedge\mathsf{val}(\mathsf{select}_{0}(t))>5,s)$
select * from s cross join t | $s\otimes t$
$\begin{array}[]{l}\text{select * from s union }\\\ \text{select * from t}\end{array}$ | $s\sqcup t$
$\begin{array}[]{l}\text{select * from s union all}\\\ \text{select * from t}\end{array}$ | $s\mathbin{\ooalign{$\sqcup$\cr\hfil\raise 1.44666pt\hbox{$\scriptscriptstyle+$}\hfil\cr}}t$
$\begin{array}[]{l}\text{select * from s intersect}\\\ \text{select * from t}\end{array}$ | $s\sqcap t$
$\begin{array}[]{l}\text{select * from s except }\\\ \text{select * from t}\end{array}$ | $s\mathbin{{\setminus}\mspace{-5.0mu}{\setminus}}t$
$\begin{array}[]{l}\text{select * from s except all}\\\ \text{select * from t}\end{array}$ | $s\setminus t$
select distinct * from s | $\mathsf{setof}(s)$
select * from s inner join t on p | $\sigma(p,s\otimes t)$
select * from s left join t on p | $\begin{array}[]{l}\sigma(p,s\otimes t)\mathbin{\ooalign{$\sqcup$\cr\hfil\raise 1.44666pt\hbox{$\scriptscriptstyle+$}\hfil\cr}}\\\ \pi(\lambda t.\langle\mathsf{select}_{0}(t),\dots\mathsf{select}_{m-1}(t),\underbrace{\mathsf{null},\dots\mathsf{null}}_{n}\rangle,\\\ s\mathbin{{\setminus}\mspace{-5.0mu}{\setminus}}(\mathsf{table.proj}_{0,\dots,m-1}(\sigma(p,s\otimes t))))\end{array}$
select * from s right join t on p | $\begin{array}[]{l}\sigma(p,s\otimes t)\quad\mathbin{\ooalign{$\sqcup$\cr\hfil\raise 1.44666pt\hbox{$\scriptscriptstyle+$}\hfil\cr}}\\\ \pi(\lambda t.\langle\underbrace{\mathsf{null},\dots\mathsf{null}}_{m},\mathsf{select}_{0}(t),\dots\mathsf{select}_{n-1}(t)\rangle,\\\ t\mathbin{{\setminus}\mspace{-5.0mu}{\setminus}}(\mathsf{table.proj}_{m,\dots,m+n-1}(\sigma(p,s\otimes t))))\end{array}$
select * from s full join t on p | $\begin{array}[]{l}\sigma(p,s\otimes t)\quad\mathbin{\ooalign{$\sqcup$\cr\hfil\raise 1.44666pt\hbox{$\scriptscriptstyle+$}\hfil\cr}}\\\ \pi(\lambda t.\langle\mathsf{select}_{0}(t),\dots\mathsf{select}_{m-1}(t),\underbrace{\mathsf{null},\dots\mathsf{null}}_{n}\rangle,\\\ s\mathbin{{\setminus}\mspace{-5.0mu}{\setminus}}(\mathsf{table.proj}_{0,\dots,m-1}(\sigma(p,s\otimes t))))\quad\mathbin{\ooalign{$\sqcup$\cr\hfil\raise 1.44666pt\hbox{$\scriptscriptstyle+$}\hfil\cr}}\\\ \\\ \pi(\lambda t.\langle\underbrace{\mathsf{null},\dots\mathsf{null}}_{m},\mathsf{select}_{0}(t),\dots\mathsf{select}_{n-1}(t)\rangle,\\\ t\mathbin{{\setminus}\mspace{-5.0mu}{\setminus}}(\mathsf{table.proj}_{m,\dots,m+n-1}(\sigma(p,s\otimes t))))\end{array}$
Figure 15: Examples of SQL translation. $m,n$ are the number of columns in
$s,t$ respectively.

######  Example .9.1 (testPushFilterThroughSemiJoin).

⬇

q1: SELECT * FROM DEPT AS DEPT INNER JOIN (SELECT EMP.DEPTNO FROM EMP AS EMP)
AS t

ON DEPT.DEPTNO = t.DEPTNO WHERE DEPT.DEPTNO <= 10;

q2: SELECT * FROM (SELECT * FROM DEPT AS DEPT0 WHERE DEPT0.DEPTNO <= 10) AS t1

INNER JOIN (SELECT EMP0.DEPTNO FROM EMP AS EMP0) AS t2

ON t1.DEPTNO = t2.DEPTNO;

The two queries above are translated into theory of tables as follows:

$\displaystyle q1$
$\displaystyle=\mathsf{bag.filter}(p_{1},\mathsf{bag.filter}(p_{0},\textit{dept}\otimes\mathsf{table.proj}_{7}(\textit{emp})))$
$\displaystyle q2$
$\displaystyle=\mathsf{bag.filter}(p_{3},\mathsf{table.proj}_{0,1}(\mathsf{bag.filter}(p_{2},\textit{dept}))\otimes\mathsf{table.proj}_{7}(\textit{emp}))$
$\displaystyle\mathsf{lift}_{0}$ $\displaystyle=\mathsf{lift}(\lambda
x,y\;.\;x\approx y,\mathsf{select}_{0}(t_{0}),\mathsf{select}_{2}(t_{0}))$
$\displaystyle\mathsf{lift}_{1}$ $\displaystyle=\mathsf{lift}(\lambda
x,y\;.\;x\leq y,\mathsf{select}_{0}(t_{1}),\mathsf{some}(10))$
$\displaystyle\mathsf{lift}_{2}$ $\displaystyle=\mathsf{lift}(\lambda
x,y\;.\;x\leq y,\mathsf{select}_{0}(t_{2}),\mathsf{some}(10))$
$\displaystyle\mathsf{lift}_{3}$ $\displaystyle=\mathsf{lift}(\lambda
x,y\;.\;x\approx y,\mathsf{select}_{0}(t_{0}),\mathsf{select}_{2}(t_{3}))$
$\displaystyle p_{i}$ $\displaystyle=\lambda
t_{i}.\mathsf{isSome}(\mathsf{lift}_{i})\wedge\mathsf{val}(\mathsf{lift}_{i}),i\in\\{0,1,2,3\\}$

Here lambda variables $t_{0},\dots,t_{3}$ may have different types. We prove
the two queries are equivalent by asserting the formula $q_{1}\not\approx
q_{2}$ in cvc5 which answers $\mathsf{unsat}$.