Abstract
Runtime Monitoring is the process of observing a system’s behavior and checking it against a formal specification. One tool to perform runtime monitoring is MonPoly, which uses metric first order temporal logic (MFOTL) as a policy specification language. MonPoly evaluates MFOTL formulas over a timestamped logs of events, or traces, that capture the system’s behavior.
Natively, the MonPoly tool supports online monitoring only via standard input and on a single machine, and does not provide a user-friendly interface to access the events it keeps track of in its state. Moreover, MonPoly provides no mechanism for updating or changing the policy being monitored. In this talk, we present a new REST-based wrapper that combines MonPoly with the time series database QuestDB to provide a flexible interface supporting both (persistent) logging and (online) monitoring of events over the network.
Our wrapper also supports policy change by starting a new instance of MonPoly and initializing its state using a fragment of the persistent logs. We present an algorithm that significantly reduces the size of the log fragment that needs to be extracted to initialize the new state. Our algorithm builds on an extension of the notion of relative intervals of MFOTL formulas introduced by Basin, Caronni, et al.
Introduction
Motivation
Our digital world consists of many hardware and software systems. These systems are continuously performing a lot of actions. For a variety of reasons one might want to monitor those actions and make sure that they do not violate some predefined specification. One way to achieve this is to log relevant actions and analyze these logs. Such monitoring is part of the field of Runtime Verification (RV) [1]. The analysis of the logs can either be done online while the system is running or it can be done offline after the system has terminated.
Consider a social media site. It is bound by an increasing number of privacy laws and regulations. Let a hypothetical piece of regulation be that a user’s location information may not be used to tailor advertisements to that user unless the user gave specific permission. Then the site could log every time instance when a user’s location data is accessed and the purpose of the access. In words the predefined specification the site wants to check then could be: "If a user’s location data is accessed and the purpose of the access is for tailoring advertisements, the user must have previously given permission for there location data to be used for advertising purposes".
MonPoly [2] is a tool for such runtime monitoring. It can perform both online and offline monitoring. For online monitoring it accepts new events via standard input. For offline monitoring it can read a timestamped log file that was generated during the runtime of a system. It uses Metric First-Order Temporal Logic (MFOTL) [6, 7, 9] as a formal specification language, which we will introduce in the background chapter.
MonPoly in its current state has some limitations that we want to improve. For one, online monitoring can not easily be done on a different machine from which the system is running on. This does not fit well with the way many modern systems operate. Modern systems are often very distributed. It is common that different functions of a system run on different machines. These can be physical or virtual machines and more and more applications are also containerized with technologies like Docker. Oftentimes multiple machines also perform the same kind of operation, e.g. caching servers. MonPoly in its current state does not fit well into this world of interconnected microservices.
Another issue that MonPoly faces currently is data portability. MonPoly can store its execution state to disk before stopping. It can also restore that state, but only on the same system as the way it stores the state is tied to the physical memory configuration of the system. We would like the ability to have MonPoly run on one system, then shut it down and restart it on a different system where it resumes with the same state that the monitor had before shutting down on the first system.
Further there is no built-in way to update the monitored policy. We aim to offer a first method for policy changes with minimal overhead in time and compute power.
We improve MonPoly in these aspects by building a wrapper that connects it with a database and also provides a new, more web friendly, interface to MonPoly. It has always been possible to use a database for logging purposes in addition to MonPoly. We integrate the logging and monitoring functionality into a single tool. This reduces potential redundancies and gives us more flexibility on the monitoring side.
MonPoly works with timestamped and tabular data. We make use of this fact for the choice of database. The temporal nature of the data leads us to time series databases, which, as the name implies, are optimized for temporal data. By far the most common type of databases are relational databases. This is a great coincidence, because relational databases make extensive use of tables for storing data. We looked at a few different relational time series databases. In the end we opted for QuestDB [16].
Our Approach
We extend MonPoly with a web based wrapper written in Python using Flask [12]. This wrapper provides a REST API [11] to MonPoly. The wrapper accepts incoming events and manages both the monitoring and logging to the database. We aim for a consistent state between the database and the monitor. Consistent here means that an event is stored in the database if and only if it has been properly processed by the monitor.
The database connection allows us to stop MonPoly on one system and resume the monitoring on a different system, by querying the database.
To facilitate some functions of the wrapper we have added some extensions to MonPoly itself. We added flags to MonPoly to print the schema of a given signature in SQL as well as JSON format. One of our aims was fault tolerance and for this we added some options to keep that would keep the monitor running instead of exiting when encountering certain issues. For the policy change we need to potentially reload a lot of events into the monitor. We added an option to first read events from a file and then switch to standard input. Previously the monitor would either read a file and then stop or continuously read from standard input. Another addition are capabilities to get the relative interval of a MFOTL formula and also to get the relative intervals of predicates in a formula. We have begun work on a different method of doing a policy change by changing only parts of a formula while MonPoly keeps running and can keep the state of the formula parts that are unchanged.
Contributions
We package MonPoly as a web app and add a new API that offers greater flexibility in how MonPoly can be used. Through this wrapper we connect MonPoly to a database. The addition of a database gives us more options in terms of data portability.
We make use of relative intervals [3] to get a good over approximation of the data needed to continue monitoring a specific formula.
With the database we can offer a first version of a policy change by stopping the monitor and starting a new instance with the events within the relative interval of the new policy already loaded.
The code base of the wrapper is in a GitLab repository [13]. The repository contains over 1300 lines of Python code. Our extended MonPoly is a branch of the development version of MonPoly on BitBucket [8]. We have added over 500 lines of code to MonPoly.
Background
Metric First-Order Temporal and Dynamic Logic
As mentioned in the introduction, Metric First-Order Temporal Logic (MFOTL) [6, 7, 9] is used as a policy specification language by MonPoly. Here we give a quick overview of MFOTL. MFOTL is well suited to express a variety of policies one might want to monitor. It combines First Order Logic (FOL) with metric temporal operators. The metric aspect of these operators is the interval they are bound by. This interval denotes a time frame in which the formula needs to be satisfied.
Metric First-Order Dynamic Logic (MFODL) [4] is an even more expressive specification language than MFOTL. MFODL introduces the notion of regular expressions. It is more general than MFOTL and in theory the temporal operators from MFOTL could be replaced by the two more powerful operators introduced by MFODL. In practice, it is often useful to keep the basic temporal operators as we can apply specialized optimizations to them that cannot be done with regular expressions.
Basin et al. [5] extends MFOTL with aggregations. Aggregation operations like SUM are commonly seen in database contexts. When considering an example like a monthly spending limit for a credit card it becomes clear how aggregations can be useful in policy monitoring.
Syntax and Semantics
Let’s recall the syntax and semantics of MFOTL [6, 7, 22] as well as MFODL [4]. Like Basin et al. [7] we let be the set of nonempty intervals over . We use the common interval definition with round brackets for open intervals and square brackets for closed ones, e.g. . A signature , as defined by Basin et al. [7], is a tuple . is a finite set of constant symbols, is a finite set of predicates, and is a function that assigns each predicate an arity . and are disjoint, i.e. . Let be a signature and a finite set of variables with . Now we have enough information to restate the definition of an MFOTL formula (Definition 2.1 in Basin et al. [7]). Let be any ordering relation over , i.e. , , . Basin et al. [7] only included the equality relation, the other comparisons were added in [4].
Definition 2.1. The MFOTL formulas over are inductively defined in the following way.
For , is a formula.
For and , is a formula.
For , if and are formulas then are formulas.
For , if and are formulas then are formulas.
Definition 2.1 omits common first order logical operators ("and") and ("for all"). These can be constructed as syntactic sugar from the three FOL operators negation, or, and the exists quantifier. The metric temporal operators in MFOTL are ("until"), ("since"), ("previous"), and ("next"). Similarly to FOL the four MFOTL operators can also be used to construct other convenient operators such as ("once"), ("eventually"), ("always"), and ("historically"). See Basin et al. [7] for the concrete derivations of these additional operators.
The subscript of the temporal operators specifies the time interval in the past or the future in which a formula must be satisfied. For the evaluation of a formula Basin et al. [7] introduces the notion of a structure over a signature . It consists of the domain and interpretations and , for each and . Basin et al. [7] further defines a temporal structure as a pair whith is a sequence of structures over and is a sequence of non-negative integers (time stamps) with the following 3 properties.
The sequence is monotonically increasing, i.e. . Moreover, makes progress for every there is some such that .
has constant domains, that is, for all , .
Each constant symbol has a rigid interpretation, that is, for all , .
A temporal structure is sometimes called a trace and denoted . It is important to note the difference between time stamps and time points. Time points are the combination of a time stamp and a structure , where is the index by which a time point is described. Since the domain of the structures and the valuation of constants do not change they are denoted as and respectively. Basin et al. defines a valuation as a mapping . And for a variable vector , and it defines the notation for the valuation that maps to for . Further it uses a notational hack to also apply a valuation to constant symbols where . For convenience, we restate Definition 2.2 from Basin et al. [7]. Since we changed the definition of a formula to include ordering relations () instead of only equality (), we append this definition to allow for that. These additions are also in Figure 1 of Basin et. al [4].
Definition 2.2. Let be a temporal structure over the signature , with and , a formula over , a valuation, and . We define the relation inductively as follows.
Analogous to Definition 2.2 we now give the definition of an MFODL formula. The definition is based on Figure 4 of Basin et al. [4], but in a notation closer to the one we already used for MFOTL formulas. For MFODL formulas we first have to define regular expressions, as MFODL formulas depend on them.
Definition 2.3. The MFODL regular expressions are defined in the following way:
If then is a regular expression.
If is a formula then is a regular expression.
If is a regular expression then is a regular expression.
If and are regular expressions then and are regular expressions.
With this we extend Definition 2.1 to include MFODL formulas.
Definition 2.4. The MFODL formulas over are inductively defined in the following way.
MFOTL formulas are also MFOTL formulas
For , if is a regular expression then and are formulas.
For the evaluation of an MFODL formula we first need to define how regular expressions get evaluated. The definition is originally given through the match function in Figure 4 of Basin et al. [4]. We formulate the definition that is more in line with the mathematical notation we used this far.
Definition 2.5. Let be a temporal structure over the signature , with and , a formula over , a valuation, and .
With the help of Definition 2.5 we can now define the evaluation of MFODL formulas which is also given in Figure 4 of Basin et al. [4] through the sat function. The trace in the sat function is simply our temporal structure . The data list is the valuation mapping. And specifies the current time point in both notations.
Definition 2.6. Let be a temporal structure over the signature , with and , a formula over , a valuation, and . We define the relation inductively as follows.
MonPoly
MonPoly [2] is a policy monitoring tool written in OCaml that supports MFOTL with aggregations and in its newest iterations it also has support for MFODL. MonPoly can monitor a fragment of MFOTL/MFODL where all future operators must be bounded. One major exception to that rule is an (implicit) always operator around the desired policy.
Let’s return to the social media example from the introduction and look at how we would go about monitoring that policy with MonPoly. We recall our description in words: "If a user’s location data is accessed and the purpose of the access is for tailoring advertisements, the user must have previously given permission for their location data to be used for advertising purposes." In MonPoly a policy is tied to a signature. A signature can be compared with a database schema and describes the arity and types of possible events. So let’s consider a possible signature for our example:
loc_accessed(user_id: int, purpose: string)
perm_granted(user_id: int)
perm_revoked(user_id: int)This is a basic signature with 3 predicates. The first one means that a users location data has been used for a specified purpose. The last two events get triggered when a user either grants or revokes permission for their location data to be used for advertising purposes. Let’s now define the policy in a formal manner.
For MonPoly we first get rid of the surrounding , because MonPoly implicitly adds an always-operator around any policy. The remaining formula in MonPoly syntax is the following:
loc_accessed(i, "advertising")
IMPLIES
(
(ONCE[0,*) perm_granted(i))
AND
(NOT (perm_revoked(i) SINCE[0,*) perm_granted(i)))
)While MonPoly cannot actually monitor this formula directly, it can monitor the negation of this formula. For this on can use the -negate flag when running MonPoly.
Time Series Databases
Time series databases are a class of databases optimized for timestamped data. For example, they optimize for data retrieval within a certain time range. With the advance of internet of things devices with built-in sensors time series databases are experiencing explosive growth. And as we have established they happen to fit well with our monitoring goals. There are many different options of time series databases available. We were looking for something with good performance, good support for tables of data, and good usability. We have opted for QuestDB [16].
QuestDB
QuestDB uses a column-based storage model [20]. It supports the PostgreSQL wire protocol [18] for querying and inserting data. This is the same protocol used by the popular relational database PostgreSQL [15]. The support for SQL as a query language is of great use, because SQL is the most widely used and taught database query language. PostgreSQL is in itself a very popular dialect of SQL and thus has a lot of tooling available which can also be used with QuestDB. It further provides a REST API [19] and has a web console for both inserting and querying data. For best performance it supports the InfluxDB Line Protocol [14, 17] with client libraries for most popular modern programming languages. InfluxDB is itself a time series database and the line protocol is a write-protocol developed by and for InfluxDB optimized for time series data. The QuestDB client libraries for different programming languages are implementations of the InfluxDB line protocol by QuestDB. QuestDB recommends using the Line Protocol for the best write performance, compared to the other methods of writing data. The Line Protocol cannot be used to query data. For that the PostgreSQL Wire Protocol is the recommended method. QuestDB is written in Java, open source, and licensed under the Apache 2.0 license.
Time Series Databases for Runtime Monitoring
In this section we explore how a time series database can be utilized in the context of runtime monitoring. We will contrast policies and database queries, as well as signatures and database schemas. An important and possibly counterintuitive thing is that MFOTL is not any more expressive than FOL. In fact, they have the same expression strength, i.e. any MFOTL formula can be expressed as a FOL formula and vice versa. Any FOL formula is by definition also a MFOTL formula. The other way around any trace in MFOTL can be simulated in FOL by extending predicates with two attributes for the time point and time stamp. Take for example the formula where is a predicate with arity . is equivalent to the FOL formula .
It is relatively straight forward to create a database schema from a signature like the one in Figure 2.1. We create one table per predicate. The predicate name is used as the table name. The columns and their types are given by the attributes. MonPoly allows for optional attribute names, we disregard those, if they are present and rely on the ordering of attributes. We need two additional columns, one for the time point, i.e. an integer index, and one for the time stamp when the event occurred. One additional table keeping track of all time points and their time stamps is necessary, because a time point could occur without any event attached to it, if we only had the events stored, we would lose any record of such time points. And any time point can influence the evaluation of a formula. This time stamp and time point table technically makes it redundant to store the time stamps with every predicate, since the mapping from time point indices to time stamps is injective. But QuestDB requires a time stamp column, and it is also beneficial for performance as QuestDB is optimized for queries on time ranges.
The database schema as SQL create statements for our example policy from Figure 2.2 can be seen in Figure 2.3. The timestamp() function is a special extension to SQL for QuestDB. It specifies the column that is used as the dedicated time stamp in a table. If it is not specified an additional time stamp column would get added. By default, no partitioning would be used.
CREATE TABLE perm_revoked(x1 INT,
time_stamp TIMESTAMP,
time_point INT)
timestamp(time_stamp);
CREATE TABLE perm_granted(x1 INT,
time_stamp TIMESTAMP,
time_point INT)
timestamp(time_stamp);
CREATE TABLE loc_accessed(x1 INT, x2 STRING,
time_stamp TIMESTAMP,
time_point INT)
timestamp(time_stamp);
CREATE TABLE ts( time_stamp TIMESTAMP,
time_point INT)
timestamp(time_stamp);Architecture
In this section we introduce the general architecture of our wrapper for MonPoly. A more in depth look at the specific technical implementation will be provided in the implementation section. In general, we have three components for this project. On one hand we have the MonPoly with a few extensions. On the other hand is QuestDB. Our wrapper acts as the glue between the two. In addition the wrapper also provides a new interface to MonPoly in the form of a REST API. Figure 3.1 shows the structure of the MonPoly wrapper.
Wrapper
The wrapper can be run directly on a system with MonPoly installed. The alternative and more portable way to run it is with a Docker container. For Docker, the MonPoly Docker image is used as a base image and then the wrapper code and the required Python libraries are installed on top. In the end the wrapper is simply run like any Flask app.
A QuestDB instance must be running separately. This can be on the same system locally or somewhere on a remote server. The connection details for QuestDB, like ports, username, database password, and hostname must be configured in the wrapper for it to be fully operational.
On a high level the user first provides the connection information for the database. Next a policy and a signature must be sent to the wrapper. If the signature and policy are monitorable, the user can issue a command to start the monitor and from this point onward the wrapper will accept and process incoming events.
At any point the user can issue a policy change by sending the appropriate command and the new policy. The wrapper will then perform the policy change and report once it is complete.
The REST API
In this section we provide a list of all the REST API endpoints, describe their purpose, and give some basic usage examples.
/This endpoint is designed to be viewed in the browser, and it displays basic information about the state of the wrapper. It shows the current policy and signature, if they have been set. Perhaps most importantly it displays the output from MonPoly./set-policyThis takes any policy or formula file for MonPoly. At this point no checks on the policy file are performed. A monitorability check is only done once both, a policy and a signature, have been set, and the user attempts to start the monitor with/start-monitor. For convenience a separate endpoint that does not start the monitor, but performs the monitorability check could be provided. Through the optionalnegateform key, the user can specify whether the negated or non-negated policy should be monitored. For this any value provided along with thenegatekey gets ignored. Se the following snippet for how/set-policycould be used with the command line tool curl [10].$ curl -X POST -F policy=@<path/to/policy> [-F negate=] <wrapper-hostname>[:port]/set-policy > {"message":"policy set to <contents of policy file>"}/set-signatureThis works very similarly to/set-policy, except it has no optional parameters likenegateand as its name describes, it sets the signature and not the policy.$ curl -X POST -F signature=@<path/to/signature> \ <wrapper-hostname>[:port]/set-signature {"message":"signature set to <contents of signature file>"}/start-monitorWith this the user can start the monitoring process. If either a policy or signature file has not been set yet, this gets reported to the user and the command exits. First a monitorability check with the provided policy and signature files is done. Any potential issues get reported back. When everything is fine, a MonPoly subprocess gets launched and the wrapper is then ready to accept and process incoming events. It is worth noting that until the monitor gets started the first time, the policy as well as the signature can be changed freely. Passing theexisting-dbargument along with this command restores the state of the monitor according to potential database entries. This can be used, when moving the wrapper from one machine to another. With this command the monitor can also be restarted on the same machine if it was stopped properly, e.g. using the/stop-monitorcommand, and the monitor state was saved to disk. Below we illustrate the basic usage for the command along with a sample response for when the command succeeds.$ curl -X GET [-F existing-db=] <wrapper-hostname>[:port]/start-monitor { "pid": <process id of MonPoly>, "args": [ <command line arguments passed to MonPoly> ] }/stop-monitorThis command stops the MonPoly subprocess in a controlled manner. It waits for any processing to be done and then attempts to stop MonPoly with itssave_and_exitcommand, which stores the memory state of MonPoly to disk./change-policyThe policy change endpoint can only be used when MonPoly is already running. Its usage is analogous toset-policy, as can be seen in the following.$ curl -X POST -F policy=@<path/to/policy> [-F negate=] <wrapper-hostname>[:port]/change-policy > {"success":"changed policy from <previous policy> to <new policy>"}The inner workings are of course different from those of
set-policy. We describe these further in the chapters on algorithms and the implementation. From a user perspective it is important to know that this command only has an effect on the monitor if the newly provided policy is monitorable against the existing signature. If not, the wrapper simply reports any potential issues back to the user and continues monitoring the old policy. An important note is that there is no way to change the signature once MonPoly has been started./get-policyand/get-signature. These command retrieve the monitored policy or signature respectively. If no policy or signature has been set yet, the returned value instead of the policy or signature is a string informing the user of that. These commands can be used like so:$ curl -X GET localhost:5000/get-policy > {"policy":"<current policy"} $ curl -X GET localhost:5000/get-signature > {"signature":"<current signature"}/reset-everythingThis is a destructive command. In a real world context this should be used exceedingly rarely. It stops any running sub-processes, deletes or resets any configuration files, and clears the database.$ curl -X GET <wrapper-hostname>[:port]/reset-everything > { "config":"deleted <path/to/config/file>", "query":<SQL query used to drop tables>, "stopped":"stopped monpoly" }/log-eventsThis is perhaps the most important endpoint. It is certainly the one that will be used the most as it is the one handling incoming events. This command takes as an argument a JSON file with a list of one or more, ordered, time points. These time points can optionally have a time stamp associated with them. For time points with no specified time stamp the wrapper assigns all them the same time stamp corresponding to the current system time. The list does not technically have to be sorted, but any out of order time points will be skipped. Time points might also be skipped if they contain predicates with unknown names, a wrong number of attributes, or the wrong types of attributes. Time points that are skipped are reported back to the user along with the reason as to why they were skipped. We aimed for a high fault tolerance in this regard. If some time points in a log file get skipped, they have no effect on the processing of time points that were in order and correctly formatted.$ curl -X POST -F events=@<path/to/JSON/log/file> \ <wrapper-hostname>[:port]/log-events > {"skipped-timepoints":<dictionary of any skipped time points>}Here we quickly describe our JSON format and how it corresponds to a MonPoly log with the help of a short example in Figure 3.2. Consider the following potential log for our ongoing example with the signature from Figure 2.1.
@10 loc_accessed(2, "advertising") (3, "navigation") @20 perm_granted(2) loc_accessed(4, "fitness-tracking") perm_revoked(3) @35 @40 perm_revoked(2)Fig 3.2Example Log in MonPoly format The same log in our JSON format can be seen in Figure 3.3. Note that in JSON we have opted for the more human-readable version of a time stamp in Unix format, whereas MonPoly internally always works with integers. Though MonPoly does provide a flag with which time stamps are displayed to the user in Unix format, for example when a policy violation occurs at a time point.
[ { "timestamp": "1970-01-01 00:00:10", "predicates": [ { "name": "loc_accessed", "occurrences": [ [2, "advertising"], [3, "navigation"] ] } ] }, { "timestamp": "1970-01-01 00:00:20", "predicates": [ { "name": "loc_accessed", "occurrences": [ [4, "fitness-tracking"] ] }, { "name": "perm_granted", "occurrences": [ [2] ] }, { "name": "perm_revoked", "occurrences": [ [3] ] } ] }, { "timestamp": "1970-01-01 00:00:35", "predicates": [] }, { "timestamp": "1970-01-01 00:00:35", "predicates": [ { "name": "perm_revoked", "occurrences": [ [2] ] } ] } ]Fig 3.3Example Log in JSON format /get-eventsThis endpoint is a direct interface to the database and queries all time points in a specified time range. The time range can be specified with optionalstartandendparameters. These parameters should be formatted just like the time stamps in our JSON log files. The time points get returned in the same JSON format as described above.$ curl -X GET [-F start=<start-date>] [-F end=<end-date>] \ <wrapper-hostname>[:port]/get-events > [<list of all time points with their events>]/get-most-recentThis command simply returns the latest time point that is stored in the database. If the database is still empty, the returned value is simplynull.$ curl -X GET <wrapper-hostname>[:port]/get-most-recent > {"response": <time stamp of newest time point, or null>}
The wrapper also provides various "getter"- and "setter"- methods for the configuration details of QuestDB. They do not change the configuration of QuestDB itself, but simply tell the wrapper how to reach QuestDB. These should be fairly self-explanatory. We will quickly list them here for completeness. For more information on what each of these values does, the QuestDB documentation [16, 17, 18] can be consulted. The QuestDB related endpoints are:
/db-set-user,
/db-set-password,
/db-set-host,
/db-set-pgsql-port,
/db-set-influxdb-port,
/db-set-database,
/db-get-user,
/db-get-password,
/db-get-host,
/db-get-pgsql-port,
/db-get-influxdb-port, and
/db-get-database.
Algorithms
Policy Change
This section gives a high level view of our policy change method. The individual parts of the policy change will be explained in the following sections of this chapter. We have a running instance of MonPoly monitoring some policy. The user asks the wrapper to monitor a new policy. The wrapper checks the monitorability of the new policy against the existing policy. If it is not monitorable the wrapper keeps the current instance of MonPoly running and reports the issue with the new policy to the user. Otherwise the wrapper uses MonPoly to get the extended relative intervals of the new policy. Then these extended relative intervals get converted to SQL queries and the wrapper runs these queries on QuestDB. The response from QuestDB gets converted into a MonPoly log file. Next the wrapper stops the current iteration of MonPoly and starts a new one that first reads the created log file. At this point the policy change is done, and the wrapper can continue with its normal operation.
Relative Intervals
First we append the definition of relative intervals from Basin et al. [3] to include all operators currently supported by MonPoly. Namely we add definitions for the MFODL operators. Intervals are defined over and can either be open or closed. The operators and are defined the same way as in Basin et al. [3]. Let and be some arbitrary intervals then and is the smallest interval containing all values in both and .
Definition 4.1. The relative interval of the formula , is defined recursively over the formula structure:
We recursively define the relative interval of regular expressions as seen in Basin et al. [4] in the following way.
Definition 4.2. The relative interval of the regular expression , is defined recursively over the structure of the regular expression:
Correctness
We want to show that it is sufficient to extract all time points with a time stamp in the relative interval for a formula from a trace to evaluate . Lemmas A.2 and A.4 in Basin et al. [3] provides exactly this. We will outline how at the end of this section.
For convenience, we restate Lemmas A.2 and A.4 as well as the definitions they require, and some auxiliary lemmas here. First we recall Definition A.2 from Basin et al. [3].
Basin et al. [3] defines a slice of a temporal structure in Definition 3.1. We restate this definition here. (In the definition is part of a signature .)
Definition 4.3. Let be a strictly increasing function, with . The temporal structure is a slice of (with respect to the function ) if and , for all and all .
Definition 4.4. Let be an interval and a trace. The T-slice of is the time slice of , where is the function and . We also require that and , for all .
We also need Definition A.4 from Basin et al. [3].
Definition 4.5. Let be an interval and . The temporal structures and are -overlapping if the following conditions hold:
and for all with .
and for all with .
Lemma A.1 in Basin et al. [3] is useful, we restate it here.
Lemma 4.1. For every formula , .
Proof The proof that this holds is a structural induction over the formula structure for both MFOTL and MFODL, except that the MFODL part requires a similar lemma for regular expressions which is mutually recursive with this one.
Lemma 4.2. For every regular expression , .
Proof For a complete proof, this proof would need to go over both, Lemma 4.1 and Lemma 4.2. The first case is a regular expression for . Trivially . Next for a formula . . By Lemma 4.1 and thus . Now we consider for two regular expressions and . By the induction hypothesis (IH) and . Thus . Finally for a regular expression . By IH . Therefore Lemma 4.2 holds for all regular expressions under the condition that Lemma 4.1 also holds.
Lemma A.2 in Basin et al. [3] goes as follows:
Lemma 4.3. Let and be intervals, a temporal structure, and a - slice of . The temporal structures and are - overlapping for all with , where is the value in Definition 4.4 used by the function with respect to and its time slice .
And finally Lemma A.4 itself.
Lemma 4.4. Let be a formula and temporal structures. If and are -overlapping, for some and , then for all valuations , it holds that iff .
A proof by structural induction on the structure of MFOTL formulas for Lemma A.4 [3] / Lemma 4.4 is provided in Basin et al. [3]. We would like to extend the lemma to MFODL formulas as well. For this an analogous lemma that works for regular expressions is needed.
Lemma 4.5. Let be a regular expression and temporal structures. If and are -overlapping, for some and , then for all valuations and , it holds that iff .
Proof Lemmas 4.4 and 4.5 are mutually recursive and must be proofed in combination by structural induction on both the structure of MFODL formulas (Definition 2.3) and the structure of regular expressions (Definition 2.4). For time reasons we forgo this proof and focus on our extension of the idea behind relative intervals in the next section.
We close this section by outlining how Lemmas 4.4, 4.5, and 4.3. For our purposes of a policy change we are essentially taking a - slice at some "current" time point with time stamp , , of some temporal structure . From Lemma 4.3 it follows that the slice and are -overlapping for the time point . And thus by the Lemmas 4.4 and 4.5 it follows that for all valuations , iff . Hence the two traces assign the formula the same truth value at the "current" time .
Relative Interval Extension
This idea of relative intervals can already filter an existing trace down to a much smaller one by removing events that are unnecessary for the evaluation of a given policy. We expand on this by creating and using a data structure that allows us to select an even smaller sub trace with the same effect of not changing the truth value of the policy.
First we move from one relative interval for an entire policy to one relative interval per predicate occurring in a policy. We break this down further. Every predicate comes with a number of attributes as defined in the signature. Some attributes are potentially constant.
Looking back at our policy from Figure 2.2, "advertising" is one such constant attribute in the predicate loc_accessed. This means any occurrence of the predicate loc_accessed where the second attribute is not "advertising", has no influence on our policy and is therefore not needed in a potential sub trace. We check every predicate in our policy for constant attributes. Then we take the set of different arrangements of constant and variable attributes per predicate. We define a structure that captures constant and variable attributes of a predicate.
Definition 4.6. Let be a signature and a predicate with arity . A mask for the predicate is a tuple with and .
is a placeholder value denoting attributes in the mask that have a non-constant value. Each mask has its own relative interval. For our example the masks with their corresponding relative intervals can be seen in Figure 4.1.
loc_accessed(*,"advertising") -> [0,0]
perm_granted(*) -> (*,0]
perm_revoked(*) -> (*,0]A * (asterisk) in the attributes denotes a variable value, in Definition 4.6. In larger formulas there can be multiple different masks per predicate. Let be the set of possible masks for a predicate .
Definition 4.7. Let and be two masks for a predicate , where is part of the signature . denotes that is no more precise than , i.e. for all with , or .
We use a map data structure to store the predicates, masks, and their respective relative intervals.
Definition 4.8. Let be a signature and let be the function that gives the set of all possible masks for a predicate . A masked predicate map is a set where with and and is an interval over .
On this data structure we define the operators , and .
Definition 4.9. Let and be two masked predicate maps and a positive interval, then
The notation denotes an element in a masked predicate map. It is equivalent to the notation , but it better shows how we are working with a map. The operator gives all the first elements, the predicate name and mask tuples, in a masked predicate map. With the help of the operators , and we now give a recursive definition for our extension of relative intervals.
We define a relation on masked predicate maps that is analogous to the subset-equals relation for intervals and illustrates that one map is contained in another.
Definition 4.10. Let and be two masked predicate maps. if for all there exists with
Lemma 4.6. Let be intervals, and a masked predicate map. Then .
Proof This follows directly from the definitions of the two operators. We omit a detailed proof.
Lemma 4.7. Let be a masked predicate map. Then .
Proof This is a direct consequence of the definition of . Adding zero to every interval in the map obviously does not change the intervals and thus it also does not change the map itself.
Lemma 4.8. Let and be masked predicate maps, then and
Proof Since the definition of is symmetric, it suffices to show on of the two relations in the lemma. From Definition 4.9 it follows that any key consisting of a predicate and a mask is also in . Since the mask is there unaltered, it satisfies the condition of being no more precise than the one in . The condition for is apparent from the definition as well, no interval is discarded and all intervals are either enlarged by the special union of intervals or kept the same.
Definition 4.11. The extended relative interval of the formula , is defined recursively over the formula structure:
And for regular expressions we define
Definition 4.12. The extended relative interval of the regular expression , is defined recursively over the structure of the regular expression:
Correctness
Analogously to regular intervals we want to use the extended relative intervals to extract (slice) a sub trace from a larger trace for a given formula that has the property that the sub trace is sufficient to evaluate the formula. We first need a few definitions and lemmas before we can proof this property.
Definition 4.13. Let be a structure over the signature , the set of interpretations for the predicate , and a mask for . The arity of , is the same as the length of the mask , . The mask matches the interpretation if for all either or , where is again the placeholder value for variable values. We write for matches .
Lemma 4.9. Let and be two masks for a predicate with , where is part of the signature . Then for every interpretation , implies that also .
Proof Note the order of appearance of and in the implication is different from that in the relation. From 4.7 it follows that for all with , either or . If then for all with either or . We now show that for all with and it also holds that either or by making a case distinction on the two possible values for each . We make a case distinction on these two options
. In this case which satisfies one of the two options of or .
. In this case or are both possible, but for both options either or .
We can thus conclude that for all with , or and thus .
Definition 4.14. Let be a masked predicate map, two time stamps, and a structure over the signature . Let be the set of all structures over the signature . is a function filtering the structure on the condition whether is in the relative intervals of the masked predicates in shifted by . Constant interpretations remain unchanged by the filtering. Concretely for all ,
Intuitively can be seen as the reference time stamp and we check whether a time stamp lies inside the relative intervals from the perspective of . The following lemma states that filtering a structure twice has the same effect as filtering once.
Lemma 4.10. Let be a structure, let be a masked predicate map and let be two time stamps. Then
Proof From Definition 4.14 we have that the constant interpretations remain unchanged by the filter operation. It remains to show that the left-hand side (LHS) and the right-hand side (RHS) in Lemma 4.10 have the same interpretations for predicates. By Definition 4.14 we have for all , And also for all , From this it is apparent that the second set of interpretations, the one filtered twice is a subset of the first one. Further by them having the same conditional part, if an interpretation is in it must also be in , because it must have already satisfied the same condition to be in .
As seen in the previous section Basin et al. [3] a -slice in Definition A.2 for slicing a temporal structure in a temporal manner. We define an analogous notion of an - slice which is a more fine-grained way of slicing that makes use of masked predicate maps.
Definition 4.15. Let be an interval, and a masked predicate map where for all , . And let a temporal structure. The - slice of is the time slice of , where is the function , and . We also require that and for all .
Definition 4.16. Let be an interval, and be a masked predicate map where for all , . Let . The temporal structures and are -overlapping if the following conditions hold:
, , and for all with ,
, and for all with ,
The next lemma establishes that a trace and its - slice are - overlapping. It is analogous to Lemma A.2 in Basin et al. [3].
Lemma 4.11. Let and be intervals, a temporal structure, and a - slice of . The temporal structures and are - overlapping, for all with , where is the value in Definition 4.16 used by the function with respect to and its slice .
Proof This proof follows the same structure as the proof to Lemma A.2 in Basin et al. [3] and the first few steps are the same. The precondition in Definition 4.16, that every interval in is contained in the interval , is satisfied, as it is also a precondition for Lemma 4.11. First we show condition 1 in Definition 4.16. For all with , it follows from that . From we get . Even more precisely for all with , we get that . From Definition 4.15 it follows that for all with . With the help of Lemma 4.7 and Definition 4.14 (shifting all intervals in a map, shifts all time stamps that fall into these intervals the same way) we can convince ourselves that the above fact implies for all with . Thus we get for all with , and with . From Lemma 4.10 it follows that for all . And with that we have shown everything for Condition 1 in Definition 4.16.
For Condition 2 we can deduce that for all with and for all with , . And because , . Hence . From Definition 4.15 it follows that for all with . Again with the help of Lemma 4.7 and Definition 4.14 we can convince ourselves that the above fact implies for all with . Thus we get And like with condition 1, from Lemma 4.10 it follows that for all . And with that we have shown everything for Condition 2 in Definition 4.16.
Analogous to Lemma A.3 in Basin et al. [3] the following Lemma states that any overlapping traces also overlap on parts of the overlapping section.
Lemma 4.12. Let and be two temporal structures that are -overlapping, for some masked predicate map , , , and . Then and are -overlapping, for each with , , and .
Proof This proof follows a similar structure as the proof of Lemma A.3 in Basin et al. [3]. We first show that Condition 1 in Definition 4.16 is satisfied, i.e. for all with , the following three things hold: , , and .
For all with , it follows that , it then follows that . From , we get , or in short . And as we know that and are -overlapping, it follows from Condition 1 in Definition 4.16 that for all with , , , and .
For any interpretation , it follows that there exists a mask for that matches and has a relative interval with . Since , there must exist a mask for with and a relative interval , for which . It follows that . And hence . From for all with and , it follows that . Moreover, we observe that for any , we have
We can convince ourselves that this holds by looking at Definitions 4.9 and 4.14. First shifts all intervals in a map. Then checks for any interpretation of a predicate if it has a matching mask in the masked predicate map and if a time stamp is in the relative interval of that mask. It is now easy to see that, if the original time stamp was in the original interval, the shifted time stamp is also in the shifted interval. And hence, by choosing , we get for all with . Since with , we get With this Condition 1 of Definition 4.16 holds for and to be - overlapping.
To show that Condition 2 of Definition 4.16 also holds, we can start by looking at all with . From our work for the first part it follows that . Hence it follows from Condition 2 of Definition 4.16 and , the observation we used to show Condition 1, and are - overlapping, that they are also - overlapping.
With this we get to the key Lemma that we rely on to make our optimization when selecting and querying a sub-trace from the database. It is analogous to Lemma A.4 in Basin et al. [3].
Lemma 4.13. Let be a formula and and temporal structures. If and are -overlapping, for some and , then for all valuations , it holds that iff .
This Lemma applies to MFOTL formulas. It can be extended to MFODL as well, but it needs a mutually recursive extensions to include regular expressions. We focus on the core MFOTL formulas.
Proof This proof is in large parts analogous to the one to Lemma A.4 in Basin et al. [3], and we follow the same structure. First we note that for the same reason as in Lemma A.4 in Basin et al. [3], the lemma’s statement is well-defined, as the definition of did not change and still includes . We proof the lemma by structural induction on the formula . In this proof is a signature, with constants , predicates , and the arity function . Similarly is the set of variables. We have the following cases.
, where . The satisfaction of depends only on the valuation . Therefore it follows that iff .
and are analogous to the first one and their detailed proofs are omitted.
, where . Since and are -overlapping it follows from Condition 1 in Definition 4.16 that , and for all with . By Definition 4.14, there exists a valuation in iff there exist , with with , and . And from the equality of the two filters given to us by Condition 1 of Definition 4.16 this is the case iff there exist , with with , and for all valuations . And further this last part holds iff . Thus, by Definition, 2.2 iff .
. and are -overlapping. By definition and . By the inductive hypothesis iff for all valuations . Therefore iff for all valuations .
. and are -overlapping. From , , , and , it follows from Lemma 4.12 that and are - and -overlapping. By the inductive hypothesis, iff and iff . Therefore iff .
. From and it follows that and are -overlapping. By the inductive hypothesis we have iff for all valuations . Thus for all , iff . By Definition 2.2 it follows directly that iff for all valuations .
. and are - overlapping, where and From and Condition 1 in Definition 4.16, it follows that .
We make a case split on the value of . If , then , for all valuations . From , and , it follows that . Since it is trivial that for all valuations .
Next we consider and make another case split on whether .
. Then and from Condition 1 in Definition 4.16 it follows that , , and hence . It further follows that and Thus by Lemma 4.12 and are - overlapping. By the induction hypothesis iff for all valuations . Because and , it follows that iff for all valuations .
. Then , for all valuations . From Condition 1 of Definition 4.16 we still have . We make a case distinction on whether or .
. In this case . Therefore , for all valuations .
. We proof this case by contradiction. Assume that . From Condition 2 in Definition 4.16 it follows that and hence . This contradicts , so it must be the case that . It follows that , for all valuations .
. The "next" case is in large parts similar to the one for "previous". Like with Lemma A.4 [3] it is simpler than "previous", because no special distinctions have to be made for and .
. Like the other cases this one is also very similar to the same case in the proof to Lemma A.4 [3] and we follow the same structure. and are - overlapping, where and From and Condition 1 in Definition 4.16 it follows that .
First we establish the two following claims, by applying the inductive hypothesis to the two sub-formulas and .
() For all with and , it holds that as well as and . We can convince ourselves that the second step in this equation holds, by considering how the operator shifts and or resizes the relative intervals inside a masked predicate map. By Lemma 4.12 and are - overlapping. It then follows from the inductive hypothesis that for all valuations .
() For all with and , it holds that as well as and . By Lemma 4.12 and are - overlapping. It follows from the inductive hypothesis that for all valuations .
We show each direction of the claimed equivalence, iff , for all valuations , separately and start with the direction from left to right. If then there is some with such that and , for all .
From it follows that and from Condition 1 in Definition 4.16 it follows that and . From Claim (i) and from it follows that .
For all , it holds that and hence . It follows from Condition 2 in Definition 4.16 that . With and Claim (ii) we get . And with that . This concludes the proof in the first direction.
Next we show the other direction of the equivalence, i.e. if then . This is equivalent to then . Like in the proof to Lemma A.4 [3], we show the second implication. From Definition 2.2 it follows that there are two possibilities for . The first is that for no , and . Or written differently, for all with , . From the Definition 4.1 it follows that for all with , . This is a useful property, because it means we can conclude from Condition 2 of Definition 4.16 that for all . And as in the proof to Lemma A.4 [3] this means that there cannot be a time stamp within the interval in that is not present in . We are currently looking at the case where for all , . Thus also for all . Combining this with Claim (i) from above we get that . And by Definition 2.2 it follows that .
The second possibility for is, that for all with and there is some with , . It follows from this that for every with , , and , there exists a with . It follows from and , that and further with the help of Definition 4.1 it follows that . From this we recall Condition 2 from Definition 4.16 and see that . Since and it follows that . By having shown that and , we can now make use of Claim (i) from above again and combine it with . It follows that . From it follows that .
We can use Claim (i) for , because and . Combining Claim (i) with yields that . And for this we have already established that there must exist a with and . It follows from that . And with it follows that . This means Claim (ii) from above is applicable to and with it, it follows from that . And thus .
. The "Until" case is analogous to the "Since" case.
For the MFODL cases, just like for "normal" regular intervals an additional lemma is needed, the proof of needs to be done over both of them, as they are mutually recursive. We state this additional lemma here, but forgo the proof for time reasons.
Lemma 4.14. Let be a regular expression and temporal structures. If and are -overlapping, for some and , then for all valuations and , it holds that iff .
We finish this section the same way we finished the section about "normal" regular intervals, by showing how the extended relative intervals can be used to extract a sub-trace that assigns a formula the same truth value at the "current" time point as the original trace. Let be the current time point with time stamp , and let be a trace, and the - slice of . Then it follows from Lemma 4.11 that and are - overlapping. And from Lemma 4.13 it follows that iff . Thus at the "current" time point with time stamp the two traces assign the formula the same truth value.
Conversion to SQL-Query
Now let’s consider how we can convert the extended relative intervals as we have them in Figure 4.1 to a SQL query. On a high level we have one SELECT query for each table corresponding to a predicate. The different masks and their relative intervals are appended as conjunctions with a single WHERE clause. Let’s assume we have a predicate with mask- relative interval tuples, . Variable values in a mask are disregarded. If the constant values in a mask have the indices , with and the relative interval is , then the corresponding SQL clause is WHERE (x<> = AND ... AND x<> AND ts >= AND ts < ). Depending on whether an interval bound is open or closed, the corresponding comparison operators are used. If an interval is unbounded, then that bound is omitted and all events are retrieved. When multiple masks and intervals for a predicate exist, multiple of the described conditions are concatenated with AND. This approach adds potentially overlapping conditions. A good query processor will hopefully recognize those and make optimizations when appropriate. We run every query for each predicate on the database. One additional query is necessary for the ts table that gets all time points in the relative interval covering the whole formula. For our example policy in Figure 2.2 with the extended relative intervals as seen in Figure 4.1 and the schema in Figure 2.3 we get the following SQL query.
FROM loc_accessed SELECT * WHERE (x2 = "advertising" AND
time_stamp >= AND
time_stamp <= )
FROM perm_granted SELECT * WHERE (time_stamp <= )
FROM perm_revoked SELECT * WHERE (time_stamp <= )
FROM ts SELECT * WHERE (time_stamp <= )The time stamp is converted to a Unix style time stamp string that can be understood by QuestDB [21].
Implementation and Evaluation
Wrapping MonPoly
We opted to use Python as a programming language for our wrapper. It is a powerful high level language that is widely used and has a large ecosystem of tools available. While we tried to keep them to a minimum, some changes directly to MonPoly itself were necessary for the wrapper to work.
The wrapper code can be divided into two core parts. The first part is responsible for providing the REST API endpoints and handling user input. One might call this part the front end of the wrapper. For this we use Flask [12], a lightweight web framework for Python. It offers a convenient way of specifying the endpoints and handling web requests.
The second part handles the interactions with MonPoly and QuestDB. One might call this the backend of the wrapper.
The distinction of these parts is reflected in the way we split the code into different files. There are just three of them, in the "src" directory of the repository [13]. The first one is "app.py" and it directly corresponds to the first part. It is conventional to have a file called "app.py". The "app.py" is to a Flask project, what a "main.py" file would be to regular python projects. Both of these are however merely conventions. Inside "app.py" there is one method for each REST API endpoint as described in the Architecture chapter.
The remaining two files, "monitor.py" and "db_helper.py" correspond to the second part from above. In "monitor.py" we define a "monitor" class, which is the heart of the wrapper. During runtime there is always one single "monitor"- object, that keeps track of everything from the current signature, the current policy, how to reach QuestDB, to a potential MonPoly subprocess. "db_helper.py" is a small class, defining a "db_helper" class that keeps track of the QuestDB configuration details, like ports, hostname, or the username. The "monitor"- class has a "db_helper"- object as a member.
The wrapper runs MonPoly as a subprocess and handles all interactions with MonPoly itself. This subprocess is a member of the "monitor"- object and any interaction with the subprocess goes through this class. Incoming events are first parsed and checked on some major formatting errors. When the formatting is deemed acceptable the events get forwarded to MonPoly on a per time point basis. If MonPoly reports an issue with a certain time stamp, either it is out of order or one event at that timestamp does not comply with the given signature, this time stamp gets ignored by MonPoly, and in turn the wrapper discards it as well. If no issue is detected with a timestamp all events in at that timestamp get forwarded to the database. Figure 5.1 illustrates the control flow of this process.
In our implementation, one "monitor" object monitors one policy at any given time. This policy can be changed, but never are there more than two policies being monitored. An obvious extension, with many perceivable applications, would be to extend the wrapper to monitor multiple policies at the same time. Multiple policies might be based on the same data, i.e. signature and it would thus be highly practical to monitor them in the same wrapper. This would remove large redundancies if the identical data doesn’t need to be stored multiple times in multiple databases.
Policy Change
The naive approach to a policy change is simply reloading all events that have ever been seen by the monitor and in turn are in the database. But we can potentially do much better than this. An initial improvement is to only load all events in the relative interval of the new policy around the most recent time point. We apply our idea of extended relative intervals to optimize the performance of this first version a policy change. This version works by stopping the current MonPoly process and starting a new one.
Additions to MonPoly
We added two flags to MonPoly that, for a signature file, produce the SQL schema, as previously described, or a representation of the signature in JSON respectively. Those flags are -sql and -sig_to_json. Their usage is shown in the following example.
$ monpoly -sql <path/to/signature>
$ monpoly -sig_to_json <path/to/signature>
The flag -sql_drop works analogous to the -sql flag and produces the SQL statements for "dropping", i.e. deleting the tables in the schema.
$ monpoly -sql_drop <path/to/signature>
The wrapper needs some kind of feedback when a time point has been processed, in order to return potential feedback to the user. We added the flag -ack_sep that can be added when starting to monitor a formula with MonPoly. A separator is a semicolon. With this flag, every time the parser reaches a semicolon, an acknowledgment gets sent to stdout. The wrapper can thus be sure that a time point has been fully processed, and no more waiting is required.
As the wrapper does not perform any check on the names, types, and arity of predicates, we want to avoid that MonPoly exits if the wrapper sends a predicate that is "faulty" in any way. For this purpose we have added a -tolerate_faulty_predicates flag. This flag makes it so that any time points that contain a predicate with wrong arity and/or types of attributes, get skipped.
Next we made some additions to make MonPoly work better for our policy change method. By default, MonPoly either runs continuously and reads input from standard input or it processes a log file and terminates once it fully processed all events in the file. We retrieve a potentially large amount of time points from the database during a policy change. It is useful if these events could be sent to MonPoly as a file. But as we want to continue monitoring after processing these past time points, MonPoly cannot terminate at this point. For this purpose we added the flag -switch_to_stdin_after_log. With this flag MonPoly processes a log file and once done with that it awaits new input from standard in. We are not necessarily interested in all the monitor verdicts of the new policy on all these past time points. Therefore we added a flag (-suppress_stdout) that suppresses any potential output while processing the time points in the log file. The output resumes normally afterwards.
The next three flags that we added concern the relative intervals and the extended relative intervals of formulas. They are -get_relative_interval, -relative_interval_per_predicate, and -relative_interval_per_predicate_json. The wrapper uses these commands to know which time points and events must be queried from the QuestDB upon a policy change.
Performance Analysis
For the performance evaluation of the wrapper there are essentially two angles to take.
RQ1 The first one is, how large is the overhead for monitoring a policy when using the wrapper compared to using MonPoly directly?
RQ2 The second point of interest is, how much can our optimizations, using extended relative intervals, improve a policy change compared to the naive approach?
Wrapper vs. MonPoly
We expect the wrapper to add a certain time overhead to the monitoring as it performs the same action as MonPoly plus some more things. We are interested in seeing how much more time these other things add to the total time. Of course, we aim for it to be as small as possible.
To get an idea of this overhead, we measure the time that the wrapper and MonPoly alone take to process equivalent traces with the same policy and signature for both. We ran 20 experiments with the same policy. For every experiment we generated increasingly long traces. In Figure 5.2 we present the average total time that the wrapper and MonPoly respectively took to process the events. We can see that the wrapper takes increasingly more time, but the growth is linear. This does not come unexpected. A constant minimal cost will always come from running the trace through a server. As an added measurement we sent every time point separately to MonPoly and measured the time for this. The idea behind this is that in our implementation this is how we forward time points to MonPoly, and we wanted to get an idea how much of the overhead this might explain. Figure 5.3 shows the same information, but averaged by the number of time points/ length of the trace. One interesting observation from this graph is the different behavior of MonPoly when processing an entire log file and when receiving individual time points continuously from standard input. For very few time points it appears that the wrapper is slightly faster than MonPoly per time point. This probably comes down to sample size.


Policy Change Performance
In this section we give an idea of the performance of the naive policy change where all events are in the database are processed compared to the performance with our optimization that uses only the events in the extended relative intervals (ERI).
We have compared a policy change using our optimizations to the naive approach by using two random policies and generating random traces of various lengths. We then compare how the two methods perform for an increasing number of time points. We have run the same randomized experiment 20 times. The setup is that we monitor a random policy and measure the time it takes to change the policy after traces with , for , time points have been stored in the database previously. Figure 5.4 shows the average time it takes to change the policy for both versions of a policy change in respect to the trace length. Figure 5.5 shows the same information, but the time has been averaged by time point. We see that there is large variation for small traces and for a bit the naive change is actually faster, but for large traces our optimization consistently beats the baseline. From the averaged graph we can’t make out much of an improvement. We do see that both get faster per time point, when there are more total time points. This can potentially be attributed to amortization costs that have to be paid for a small number as well as for a large number of time points. Of course the expected performance improvement depends heavily on the formula, if it has large extended relative intervals it is barely different from the naive case, and also on the size of the trace stored in the database.


Partial Policy Change
We have started looking into a different method for a policy change that could be done directly through MonPoly and would not rely on the wrapper and the presence of a database. The general idea is that in many use cases it is common that a policy is made up of many individual parts and one might want to change only a small part of a formula. Consider for example a privacy policy on a website. Let’s say a user has the ability to specify where their data may and may not be used. Maybe they had selected very restrictive options, but now want to allow their data to be used in one specific case. MonPoly has now continuously been monitoring the restrictive policy and also has the state for all the sub-formulas in the larger policy. In terms of efficiency it would be useful, if the state would only need to be recomputed for the one part that got changed and if the rest of the state could be kept.
One case might be where policies are all in conjunctive normal form (CNF) and single conjuncts might get added or removed. To remove a conjunct from the formula it needs some sort of identifier. In a regular structure like a CNF formula this could be done by automatic indexing. But it still poses some questions, like what happens if the monitor rewrites the formula to an equivalent one, but changes the order. Then the user doesn’t have an inherent idea of a conjuncts’ location anymore. Our solution to this problem was thus to let the user provide identifiers in the form of strings for certain sub-formulas.
We have begun implementing this change in MonPoly. Our idea makes use of the existing commands feature that lets a user control certain aspects of MonPoly during its runtime. We envision commands of the form "remove sub-formula x", "add formula y as a conjunct to sub-formula x". The second example would replace place the sub formula "x and y" in place of "x". An analogous thing for "or" with an "add disjunct" command is also perceivable. Or also a command like "negate sub-formula x".
With all this, MonPoly would parse the new formula part, add it to the existing formula, check if the new formula is monitorable, and if so it updates the policy. Similarly if a part gets removed a check on monitorability of the remaining formula needs to be done. Before adding a sub-formula, the existing trace has to be checked against that sub-formula and this state must get combined with the pre-existing state of MonPoly.
We have started implementing a feature that allows for named formulas inside MonPoly. The names should have no effect on the monitoring and solely act as the identifiers of formula parts. For this we extended formula in MonPoly by an additional type, NamedFormula of (string * formula). And similarly we added the type ENamedExtf of string * extformula * int to extformula.
To specify a named (sub)formula in a MonPoly policy, we have extended the formula parser and lexer to accept formulas with the following syntax,
NAME[f1, name1] AND NAME[f2 OR f3, name2].
Conclusion
To recap, we have set out to build a wrapper around MonPoly that handles persistent data storage, offers a web friendly interface to MonPoly, and provides a policy change method. MonPoly is a runtime monitoring tool that uses MFOTL (and in its newest version also MFODL) as a policy specification language. MFOTL and MFODL are powerful, as in they can express a large amount of properties.
The amount of computer systems in the world is only growing and with it the need for security guarantees is also increasing. While MonPoly does not directly offer such guarantees, it is a useful tool in detecting policy violations.
Considering that a runtime monitor and a database storing system activities often rely on the same data, the idea to combine storing events and monitoring them is a natural one. Some regulation, like GDPR, also requires logging of certain information. This combination of technologies also offers new possibilities, that were not easily achievable before. One such thing is a policy change. When past data can simply be read from the database, it becomes easy to restore the same state when starting to monitor a new policy.
There are many points of future interest around the wrapper specifically and more generally about policy change. As far as the wrapper is concerned, we have already briefly mentioned that one natural expansion would be to monitor multiple policies at the same time. The wrapper would be well suited to abstract away the intricacies and provide a simple interface to the user.
An obvious area for future work is our partial policy change, the core idea of which is outlined at the end of chapter 3. Such an approach may be sufficient to achieve ideal performance. Data protection, where a user can add or remove certain permissions, can be one such use case.
References
- Bartocci, Ezio, Yliès Falcone, Adrian Francalanza, and Giles Reger. 2018. Lectures on Runtime Verification. Edited by Ezio Bartocci and Yliès Falcone. Vol. 10457. Springer International Publishing. https://doi.org/10.1007/978-3-319-75632-5.
- Basin, David A, Felix Klaedtke, and Eugen Zalinescu. 2017. “The MonPoly Monitoring Tool.” RV-CuBES 3: 19–28.
- Basin, David, Germano Caronni, Sarah Ereth, Matúš Harvan, Felix Klaedtke, and Heiko Mantel. 2016. “Scalable Offline Monitoring of Temporal Specifications.” Formal Methods in System Design 49: 75–108.
- Basin, David, Thibault Dardinier, Lukas Heimes, Srđan Krstić, Martin Raszyk, Joshua Schneider, and Dmitriy Traytel. 2020. “A Formally Verified, Optimized Monitor for Metric First-Order Dynamic Logic.” In Automated Reasoning: 10th International Joint Conference, IJCAR 2020, Paris, France, July 1–4, 2020, Proceedings, Part i 10, 432–53. Springer.
- Basin, David, Felix Klaedtke, Srdjan Marinovic, and Eugen Zălinescu. 2015. “Monitoring of Temporal First-Order Properties with Aggregations.” Formal Methods in System Design 46: 262–85.
- Basin, David, Felix Klaedtke, Samuel Müller, and Birgit Pfitzmann. 2008. “Runtime Monitoring of Metric First-Order Temporal Properties.” In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
- Basin, David, Felix Klaedtke, Samuel Müller, and Eugen Zălinescu. 2015. “Monitoring Metric First-Order Temporal Properties.” Journal of the ACM (JACM) 62: 1–45.
- “BitBucket MonPoly Branch.” n.d. https://bitbucket.org/jshs/monpoly/commits/branch/BA_logging_backend.
- Chomicki, Jan. 1995. “Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding.” ACM Transactions on Database Systems (TODS) 20: 149–86.
- “Curl.” n.d. https://curl.se/.
- Fielding, Roy Thomas. 2000. Architectural Styles and the Design of Network-Based Software Architectures. University of California, Irvine.
- “Flask.” n.d. https://flask.palletsprojects.com/.
- “GitLab MonPoly Wrapper.” n.d. https://gitlab.inf.ethz.ch/fhublet/monpoly-server.
- “InfluxDB Line Protocol.” n.d. https://docs.influxdata.com/influxdb/v1.8/write_protocols/line_protocol_tutorial/.
- “PostgreSQL.” n.d. https://www.postgresql.org/.
- “QuestDB.” n.d. https://questdb.io/.
- “QuestDB - InfluxDB Line Protocol.” n.d. https://questdb.io/docs/reference/api/ilp/overview/.
- “QuestDB - Postgres Wire Protocol.” n.d. https://questdb.io/docs/reference/api/postgres/.
- “QuestDB - REST API.” n.d. https://questdb.io/docs/reference/api/rest/.
- “QuestDB - Storage Model.” n.d. https://questdb.io/docs/concept/storage-model/.
- “QuestDB - Time Stamps.” n.d. https://questdb.io/docs/reference/function/date-time/#date-and-timestamp-format.
- Schneider, Joshua, David Basin, Srđan Krstić, and Dmitriy Traytel. 2019. “A Formally Verified Monitor for Metric First-Order Temporal Logic.” In Runtime Verification: 19th International Conference, RV 2019, Porto, Portugal, October 8–11, 2019, Proceedings 19, 310–28. Springer.