A Real-Time, Flexible Logging Infrastructure for MonPoly

The talk on the bachelor's thesis: a wrapper that combines the MonPoly monitor with the time series database QuestDB

Jonas DegeloBachelor's thesis talk, ETH ZurichFebruary 24, 2023

Read the thesisOriginal slides

Scroll

Background and motivation

2

The monitoring problem

  • Runtime monitoring checks a system's actual behaviour against a formal specification.
  • Online monitoring is done while the system is running.
  • Offline monitoring is done on a log after the system has completed.

We focus on the online monitoring problem.

3

MonPoly

MonPoly is a runtime monitor. Its policies are written in metric first-order temporal logic (MFOTL), which adds temporal operators to first-order logic. Each operator carries an interval II that restricts the time points relevant to it.

Next∘I φ\Next{I}\, \varphiAlways□I φ\Always{I}\, \varphi
Previous∙I φ\Previous{I}\, \varphiHistorically■I φ\Historically{I}\, \varphi
Untilφ UI ψ\varphi \Until{I} \psiEventually◊I φ\Eventually{I}\, \varphi
Sinceφ SI ψ\varphi \Since{I} \psiOnce⧫I φ\Once{I}\, \varphi

The temporal operators are on the left, the syntactic sugar built from them on the right.

  • Time point: a time-stamped collection of events (predicates), often referred to by an integer index.
  • Time stamp: a moment in time, e.g. seconds since the Unix epoch.
4

The thesis defines the logic in §2.1 Metric First-Order Temporal and Dynamic Logic and introduces the tool in §2.2 MonPoly.

Time-series databases

A time-series database is optimized for inserting and retrieving temporal data. We use QuestDB:

  • It is largely compatible with PostgreSQL.
  • It adds a TIMESTAMP data type to the usual types INT, STRING, etc.
  • Each table has a dedicated time stamp column, analogous to an index column.
5

More in §2.3.1 QuestDB.

Monitor vs. database

Monitor (MonPoly)Time-series database (QuestDB)
Good whendata changes often
the policy changes rarely
data stays almost constant
queries vary and are frequent
Bad whenthe policy changes frequentlydata changes rapidly
6

Combining monitoring and a time-series database

We build a wrapper that logs and monitors the same data. It:

  • provides the functionality of both a monitor and a time-series database,
  • allows us to offer a policy change method,
  • gives MonPoly a more accessible interface, for web services and distributed systems,
  • increases fault tolerance.
7

From signature to database schema

Each predicate of a MonPoly signature becomes a table, with one column per attribute plus the time point tp and the time stamp ts. One more table records every time point, including those without events.

schema.sql
CREATE TABLE P(x1 INT, x2 STRING,
               tp INT,
               ts TIMESTAMP)
               timestamp(ts);
CREATE TABLE Q(x1 INT, x2 INT,
               tp INT,
               ts TIMESTAMP)
               timestamp(ts);
CREATE TABLE R(x1 INT, x2 STRING,
               x3 STRING,
               tp INT,
               ts TIMESTAMP)
               timestamp(ts);
CREATE TABLE time_points
               (tp INT,
               ts TIMESTAMP)
               timestamp(ts);
signature.sig
P(id:int, act:string)
Q(id1:int, id2:int)
R(int, string, string)
8

The thesis explains the mapping in §2.3.2 Time Series Databases for Runtime Monitoring.

Agenda

  1. The wrapper: its REST API, architecture and data flow.
  2. Algorithm and policy change: relative intervals and their extension.
  3. Partial policy change: work in progress inside MonPoly.
  4. Evaluation and outlook.
9

The wrapper

10

The REST API

Monitor and logQuestDB connection
/ (info page)/db-set-user
/set-policy/db-set-password
/set-signature/db-set-host
/start-monitor/db-set-pgsql-port
/stop-monitor/db-set-influxdb-port
/change-policy/db-set-database
/get-policy/db-get-user
/get-signature/db-get-password
/reset-everything/db-get-host
/log-events/db-get-pgsql-port
/get-events/db-get-influxdb-port
/get-most-recent/db-get-database
11

Every endpoint is described, with example calls, in §3.2 The REST API.

Architecture

User Wrapper Check JSON formatting Convert JSON to MonPoly log MonPoly Check monitorability of policies Compute relative intervals (for policy change) QuestDB Keeps a copy of the trace already processed by MonPoly events /signature / policy events /signature /policy monitor verdict /monitorability /relative intervals monitoredevents query response

Data flow

The wrapper checks incoming events before they reach MonPoly, and faulty input is reported instead of stopping the monitor: fault tolerance increases compared to MonPoly alone.

Wrapper parsesJSONRequired keyspresent?Send event toMonPolyIn order?Signaturecompliant?Report monitorverdict to user;forward eventto QuestDBReport faultyJSON formattingReport out-of-ordertime stampReport faultypredicate yesyesyesnonono

Algorithm and policy change

14

Policy change

  • A policy change starts a new monitor with the new policy.
  • Goal: the new monitor evaluates the new policy at the current time point just as if it had seen the same trace as the old monitor.
  • Naive approach: read the entire trace again.
  • Idea: reduce the trace by removing events that do not influence how the new policy is evaluated.

Optimization example

φ=(P(x,“a”) S[0,30) Q(x,2))∧(¬R(y,“c”,z) S[20,60) P(y,z))\phi = (P(x, \text{“a”}) \Since{[0,30)} Q(x, 2)) \land (\neg R(y, \text{“c”}, z) \Since{[20,60)} P(y, z))
  • Relative interval: RI⁡(φ)=(−60,0]\RI(\phi) = (-60, 0]
  • Extended relative intervals: ERI⁡(φ)=amp;P(∗,∗)amp;amp;→(−60,−20]amp;P(∗,“a”)amp;amp;→(−30,0]amp;Q(∗,2)amp;amp;→(−30,0]amp;R(∗,“c”,∗)amp;amp;→(−60,0]\ERI(\phi) = \begin{alignedat}{2} &P(*,*) &&\to (-60,-20] \\ &P(*,\text{“a”}) &&\to (-30,0] \\ &Q(*,2) &&\to (-30,0] \\ &R(*,\text{“c”},*) &&\to (-60,0] \end{alignedat}

Time points whose time stamps lie outside {current time stamp}⊕RI⁡(φ)\{\text{current time stamp}\} \oplus \RI(\phi) do not change the evaluation of φ\phi at the current time point.

16

Interval operators

Let II and JJ be two intervals. Then

  • I⊕J={i+j∣i∈I,j∈J}I \oplus J = \{i + j \mid i \in I, j \in J\}, for example [0,3]⊕[−2,4]=[−2,7][0,3] \oplus [-2,4] = [-2,7];
  • I⋓JI \Cup J is the smallest interval that contains every element of II or JJ, for example [−4,1]⋓[4,5]=[−4,5][-4,1] \Cup [4,5] = [-4,5].
17

Relative intervals

The relative interval of a formula φ\phi, RI⁡(φ)⊆Z\RI(\phi) \subseteq \mathbb{Z}, is defined inductively over the formula structure [3]:

RI⁡(φ)={{0}amp;atomic formulasRI⁡(ψ)amp;¬ψ, ∃x.ψ, ∀x.ψRI⁡(ψ)⋓RI⁡(χ)amp;ψ∨χ, ψ∧χ(−b,0]⋓((−b,−a]⊕RI⁡(ψ))amp;∙[a,b)ψ[0,b)⋓([a,b)⊕RI⁡(ψ))amp;∘[a,b)ψ(−b,0]⋓((−b,0]⊕RI⁡(ψ))⋓((−b,−a]⊕RI⁡(χ))amp;ψ S[a,b) χ[0,b)⋓([0,b)⊕RI⁡(ψ))⋓([a,b)⊕RI⁡(χ))amp;ψ U[a,b) χ\RI(\phi) = \begin{cases} \{0\} & \text{atomic formulas} \\ \RI(\psi) & \neg \psi,\ \exists x.\psi,\ \forall x.\psi \\ \RI(\psi) \Cup \RI(\chi) & \psi \lor \chi,\ \psi \land \chi \\ (-b,0] \Cup ((-b,-a] \oplus \RI(\psi)) & \Previous{[a,b)} \psi \\ [0,b) \Cup ([a,b) \oplus \RI(\psi)) & \Next{[a,b)} \psi \\ (-b,0] \Cup ((-b,0] \oplus \RI(\psi)) \Cup ((-b,-a] \oplus \RI(\chi)) & \psi \Since{[a,b)} \chi \\ [0,b) \Cup ([0,b) \oplus \RI(\psi)) \Cup ([a,b) \oplus \RI(\chi)) & \psi \Until{[a,b)} \chi \end{cases}
18

Definition 4.1 in the thesis also covers the MFODL operators.

Extended relative intervals: operators

A map from masked predicates to intervals replaces the single interval, so new operators are needed. Let MM and NN be two masked predicate maps and TT an interval:

M ⋓¨ N=amp;{p(l)→(I⋓J)∣p(l)→I∈M and p(l)→J∈N}amp;∪{p(l)→I∣p(l)→I∈M and p(l)∈keys⁡(M)∖keys⁡(N)}amp;∪{p(l)→I∣p(l)→I∈N and p(l)∈keys⁡(N)∖keys⁡(M)}T ⋓˙ M=amp;{p(l)→(T⋓I)∣p(l)→I∈M}T ⊕˙ M=amp;{p(l)→(T⊕I)∣p(l)→I∈M}\begin{aligned} M \Cupmerge N = {} & \{ p(l) \to (I \Cup J) \mid p(l) \to I \in M \text{ and } p(l) \to J \in N \} \\ & \cup \{ p(l) \to I \mid p(l) \to I \in M \text{ and } p(l) \in \keys(M) \setminus \keys(N) \} \\ & \cup \{ p(l) \to I \mid p(l) \to I \in N \text{ and } p(l) \in \keys(N) \setminus \keys(M) \} \\ T \Cupext M = {} & \{ p(l) \to (T \Cup I) \mid p(l) \to I \in M \} \\ T \oplusext M = {} & \{ p(l) \to (T \oplus I) \mid p(l) \to I \in M \} \end{aligned}

Extended relative intervals

The definition follows that of relative intervals; what changes is marked.

ERI⁡(φ)={\acc{}amp;other atomic formulas\acc{p(m)→[0,0]}amp;predicate p, mask mERI⁡(ψ)amp;¬ψ, ∃x.ψ, ∀x.ψERI⁡(ψ)\acc ⋓¨ ERI⁡(χ)amp;ψ∨χ, ψ∧χ(−b,0]\acc ⋓˙ ((−b,−a]\acc ⊕˙ ERI⁡(ψ))amp;∙[a,b)ψ[0,b)\acc ⋓˙ ([a,b)\acc ⊕˙ ERI⁡(ψ))amp;∘[a,b)ψ(−b,0]\acc ⋓˙ ((−b,0]\acc ⊕˙ ERI⁡(ψ))\acc ⋓¨ ((−b,−a]\acc ⊕˙ ERI⁡(χ))amp;ψ S[a,b) χ[0,b)\acc ⋓˙ ([0,b)\acc ⊕˙ ERI⁡(ψ))\acc ⋓¨ ([a,b)\acc ⊕˙ ERI⁡(χ))amp;ψ U[a,b) χ\ERI(\phi) = \begin{cases} \acc{\{\}} & \text{other atomic formulas} \\ \acc{\{p(m) \to [0,0]\}} & \text{predicate pp, mask mm} \\ \ERI(\psi) & \neg \psi,\ \exists x.\psi,\ \forall x.\psi \\ \ERI(\psi) \acc{\Cupmerge} \ERI(\chi) & \psi \lor \chi,\ \psi \land \chi \\ (-b,0] \acc{\Cupext} ((-b,-a] \acc{\oplusext} \ERI(\psi)) & \Previous{[a,b)} \psi \\ [0,b) \acc{\Cupext} ([a,b) \acc{\oplusext} \ERI(\psi)) & \Next{[a,b)} \psi \\ (-b,0] \acc{\Cupext} ((-b,0] \acc{\oplusext} \ERI(\psi)) \acc{\Cupmerge} ((-b,-a] \acc{\oplusext} \ERI(\chi)) & \psi \Since{[a,b)} \chi \\ [0,b) \acc{\Cupext} ([0,b) \acc{\oplusext} \ERI(\psi)) \acc{\Cupmerge} ([a,b) \acc{\oplusext} \ERI(\chi)) & \psi \Until{[a,b)} \chi \end{cases}

We proved that this definition is a correct approximation: it extracts all time points from a trace that are needed, and φ\phi evaluates the same on the original trace and on the extraction.

Extended relative intervals in the example

φ=(P(x,“a”) S[0,30) Q(x,2))∧(¬R(y,“c”,z) S[20,60) P(y,z))\phi = (P(x, \text{“a”}) \Since{[0,30)} Q(x, 2)) \land (\neg R(y, \text{“c”}, z) \Since{[20,60)} P(y, z))
  • Relative interval: RI⁡(φ)=\blu(−60,0]\RI(\phi) = \blu{(-60,0]}
  • Extended relative intervals: ERI⁡(φ)=amp;P(∗,∗)amp;amp;→\acc(−60,−20]amp;P(∗,\acc“a”)amp;amp;→\acc(−30,0]amp;Q(∗,\acc2)amp;amp;→\acc(−30,0]amp;R(∗,\acc“c”,∗)amp;amp;→\acc(−60,0]\ERI(\phi) = \begin{alignedat}{2} &P(*,*) &&\to \acc{(-60,-20]} \\ &P(*,\acc{\text{“a”}}) &&\to \acc{(-30,0]} \\ &Q(*,\acc{2}) &&\to \acc{(-30,0]} \\ &R(*,\acc{\text{“c”}},*) &&\to \acc{(-60,0]} \end{alignedat}
21

What the query keeps

On a random trace, each masked predicate keeps only the events in its own interval. Everything else in (−60,0](-60, 0] is skipped, although the plain relative interval would read it. An event appears in every row whose mask it matches.

RI(φ) = (−60, 0]: the plain relative interval keeps all of thisP(*,*)→ (−60, −20]P(*,“a”)→ (−30, 0]Q(*,2)→ (−30, 0]R(*,“c”,*)→ (−60, 0]other eventsQ(*,5), R(*,“d”,*)−60−50−40−30−20−10nowneeded by φnot neededThe query reads 8 of the 19 events in (−60, 0].
22

The thesis shows the same picture next to §4.3 Relative Interval Extension.

From extended relative intervals to SQL

Each masked predicate becomes a condition on its table; the time points table is queried with the relative interval of the whole formula.

SELECT * FROM P WHERE
    (time_stamp > <NOW>-60 AND time_stamp <= <NOW>-20)
    OR
    (x2 = "a" AND
    time_stamp > <NOW>-30 AND time_stamp <= <NOW>-0);
SELECT * FROM Q WHERE
    (x2 = 2 AND
    time_stamp > <NOW>-30 AND time_stamp <= <NOW>-0);
SELECT * FROM R WHERE
    (x2 = "c" AND
    time_stamp > <NOW>-60 AND time_stamp <= <NOW>-0);
SELECT * FROM time_points WHERE
    (time_stamp > <NOW>-60 AND time_stamp <= <NOW>-0);

Converting the database result

QuestDB's answer is turned into the wrapper's JSON log format, and from there into a MonPoly log that the new monitor reads before it switches to standard input.

QuestDB response
[{"R":[]},
 {"Q":[[0,8,65536,"Thu, 01 Jan 1970 00:00:01 GMT"]]},
 {"P":[]},
 {"time_points":[[65536,"Thu, 01 Jan 1970 00:00:01 GMT"],
                 [65537,"Thu, 01 Jan 1970 00:00:02 GMT"]]}]
wrapper.json
[{"predicates":[{"name":"Q","occurrences":[[0,8]]}],
  "timepoint":65536,"timestamp":"1970-01-01 00:00:01"},
 {"predicates":[],
  "timepoint":65537,"timestamp":"1970-01-01 00:00:02"}]
monpoly.log
@1 Q(0,8);
@2 ;
24

Partial policy change (work in progress)

25

Partial policy change in MonPoly

  • Only for first-order logic operators above temporal operators.
  • Named formulas: NAME[f1, name1] OR NAME[f2 AND f3, name2]
  • We added data types for NAME to MonPoly and updated the formula parser for NAME constructs.
  • We started work on commands that add or remove conjuncts and disjuncts:
>remove_part <name><
>add_conjunct <name1> <name2> <formula><
>add_disjunct <name1> <name2> <formula><

Partial policy change: example

φ=(P(x,“a”) S[0,30) Q(x,2))∧(¬R(y,“c”,z) S[20,60) P(y,z))\phi = (P(x, \text{“a”}) \Since{[0,30)} Q(x, 2)) \land (\neg R(y, \text{“c”}, z) \Since{[20,60)} P(y, z))

With names for its parts, the policy becomes

NAME[(P(x,"a") SINCE[0,30) Q(x,2)), part1] AND
NAME[(NOT (R(y,"c",z)) SINCE[20,60) P(y,z)), part2]
command
>add_disjunct part1 part3 'NOT P(2,"b")'<
result
(NAME[P(x,"a") SINCE[0,30) Q(x,2), part1] OR
 NAME[NOT P(2,"b"), part3]) AND
NAME[NOT (R(y,"c",z)) SINCE[20,60) P(y,z), part2]
φ′=((P(x,“a”) S[0,30) Q(x,2))∨¬P(2,“b”))∧(¬R(y,“c”,z) S[20,60) P(y,z))\phi' = ((P(x, \text{“a”}) \Since{[0,30)} Q(x, 2)) \lor \neg P(2, \text{“b”})) \land (\neg R(y, \text{“c”}, z) \Since{[20,60)} P(y, z))
27

Partial policy change: next steps

  • Compute the internal state for formula parts that are added.
  • Combine the existing state with the state of the new formula.
  • Update the state when a formula part is removed.
28

Evaluation

29

Overhead of the wrapper

  • A random policy with intervals bounded by [0,20)[0,20).
  • A random trace with 4i4^i time points, for i=0,…,8i = 0, \dots, 8.
  • We measure the time MonPoly takes to monitor these traces;
  • the time MonPoly takes when the time points are sent individually instead of in one file, which better simulates online monitoring;
  • and the time the wrapper takes to monitor the traces.
  • This was done 100 times, with 100 different policies.
30

The thesis reports this experiment in §5.4.1 Wrapper vs. MonPoly.

Overhead of the wrapper: results

Average time per time point against the number of time points in the trace, log-log: MonPoly reading a file falls from about 3 ms to under 10 µs; MonPoly with time points sent individually stays near 50 to 100 µs; the wrapper falls from about 4 ms to about 130 µs.
Average time per time point
31

Overhead of the wrapper: conclusion

More detailed profiling is required. Possible sources of the overhead:

  • converting our JSON log format to the MonPoly format;
  • the wrapper sends time points to MonPoly synchronously;
  • the wrapper goes over the events once to send them to MonPoly and again later to send them to QuestDB.
32

Policy change optimization

  • A policy change between 2 randomly generated formulas.
  • Intervals in the policies are bounded by [0,20)[0,20).
  • Random traces with 4i4^i time points, for i=0,…,8i = 0, \dots, 8.
  • Load the trace into the wrapper, then start the policy change.
  • This was done 100 times, for 100 different policy pairs.

Policy change optimization: results

Run time for a policy change against the number of time points in the trace, log-log: the naive approach grows from about 0.02 s to about 2 s at 65,536 time points, while the optimization stays near 0.025 s throughout.
Run time for a policy change
34

Outlook

35

Outlook

  • Reduce the overhead of the wrapper: profile it in more depth, and send time points asynchronously, without waiting for a response before sending the next one.
  • Speed up the policy change: check constraints on variables in formulas, such as x<20x \lt 20, more thoroughly.
  • Continue the partial policy change within MonPoly.
36

The thesis closes with §6 Conclusion.