| 1 |
Runtime Verification Monitor Synthesis |
| 2 |
====================================== |
| 3 |
|
| 4 |
The starting point for the application of runtime verification (RV) techniques |
| 5 |
is the *specification* or *modeling* of the desired (or undesired) behavior |
| 6 |
of the system under scrutiny. |
| 7 |
|
| 8 |
The formal representation needs to be then *synthesized* into a *monitor* |
| 9 |
that can then be used in the analysis of the trace of the system. The |
| 10 |
*monitor* connects to the system via an *instrumentation* that converts |
| 11 |
the events from the *system* to the events of the *specification*. |
| 12 |
|
| 13 |
|
| 14 |
In Linux terms, the runtime verification monitors are encapsulated inside |
| 15 |
the *RV monitor* abstraction. The RV monitor includes a set of instances |
| 16 |
of the monitor (per-cpu monitor, per-task monitor, and so on), the helper |
| 17 |
functions that glue the monitor to the system reference model, and the |
| 18 |
trace output as a reaction to event parsing and exceptions, as depicted |
| 19 |
below:: |
| 20 |
|
| 21 |
Linux +----- RV Monitor ----------------------------------+ Formal |
| 22 |
Realm | | Realm |
| 23 |
+-------------------+ +----------------+ +-----------------+ |
| 24 |
| Linux kernel | | Monitor | | Reference | |
| 25 |
| Tracing | -> | Instance(s) | <- | Model | |
| 26 |
| (instrumentation) | | (verification) | | (specification) | |
| 27 |
+-------------------+ +----------------+ +-----------------+ |
| 28 |
| | | |
| 29 |
| V | |
| 30 |
| +----------+ | |
| 31 |
| | Reaction | | |
| 32 |
| +--+--+--+-+ | |
| 33 |
| | | | | |
| 34 |
| | | +-> trace output ? | |
| 35 |
+------------------------|--|----------------------+ |
| 36 |
| +----> panic ? |
| 37 |
+-------> <user-specified> |
| 38 |
|
| 39 |
RV monitor synthesis |
| 40 |
-------------------- |
| 41 |
|
| 42 |
The synthesis of a specification into the Linux *RV monitor* abstraction is |
| 43 |
automated by the rvgen tool and the header file containing common code for |
| 44 |
creating monitors. The header files are: |
| 45 |
|
| 46 |
* rv/da_monitor.h for deterministic automaton monitor. |
| 47 |
* rv/ltl_monitor.h for linear temporal logic monitor. |
| 48 |
|
| 49 |
rvgen |
| 50 |
----- |
| 51 |
|
| 52 |
The rvgen utility converts a specification into the C presentation and creating |
| 53 |
the skeleton of a kernel monitor in C. |
| 54 |
|
| 55 |
For example, it is possible to transform the wip.dot model present in |
| 56 |
[1] into a per-cpu monitor with the following command:: |
| 57 |
|
| 58 |
$ rvgen monitor -c da -s wip.dot -t per_cpu |
| 59 |
|
| 60 |
This will create a directory named wip/ with the following files: |
| 61 |
|
| 62 |
- wip.h: the wip model in C |
| 63 |
- wip.c: the RV monitor |
| 64 |
|
| 65 |
The wip.c file contains the monitor declaration and the starting point for |
| 66 |
the system instrumentation. |
| 67 |
|
| 68 |
Similarly, a linear temporal logic monitor can be generated with the following |
| 69 |
command:: |
| 70 |
|
| 71 |
$ rvgen monitor -c ltl -s pagefault.ltl -t per_task |
| 72 |
|
| 73 |
This generates pagefault/ directory with: |
| 74 |
|
| 75 |
- pagefault.h: The Buchi automaton (the non-deterministic state machine to |
| 76 |
verify the specification) |
| 77 |
- pagefault.c: The skeleton for the RV monitor |
| 78 |
|
| 79 |
Monitor header files |
| 80 |
-------------------- |
| 81 |
|
| 82 |
The header files: |
| 83 |
|
| 84 |
- `rv/da_monitor.h` for deterministic automaton monitor |
| 85 |
- `rv/ltl_monitor` for linear temporal logic monitor |
| 86 |
|
| 87 |
include common macros and static functions for implementing *Monitor |
| 88 |
Instance(s)*. |
| 89 |
|
| 90 |
The benefits of having all common functionalities in a single header file are |
| 91 |
3-fold: |
| 92 |
|
| 93 |
- Reduce the code duplication; |
| 94 |
- Facilitate the bug fix/improvement; |
| 95 |
- Avoid the case of developers changing the core of the monitor code to |
| 96 |
manipulate the model in a (let's say) non-standard way. |
| 97 |
|
| 98 |
rv/da_monitor.h |
| 99 |
+++++++++++++++ |
| 100 |
|
| 101 |
This initial implementation presents three different types of monitor instances: |
| 102 |
|
| 103 |
- ``#define RV_MON_TYPE RV_MON_GLOBAL`` |
| 104 |
- ``#define RV_MON_TYPE RV_MON_PER_CPU`` |
| 105 |
- ``#define RV_MON_TYPE RV_MON_PER_TASK`` |
| 106 |
|
| 107 |
The first sets up functions declaration for a global deterministic automata |
| 108 |
monitor, the second for monitors with per-cpu instances, and the third with |
| 109 |
per-task instances. |
| 110 |
|
| 111 |
In all cases, the C file must include the $(MODEL_NAME).h file (generated by |
| 112 |
`rvgen`), for example, to define the per-cpu 'wip' monitor, the `wip.c` source |
| 113 |
file must include:: |
| 114 |
|
| 115 |
#define RV_MON_TYPE RV_MON_PER_CPU |
| 116 |
#include "wip.h" |
| 117 |
#include <rv/da_monitor.h> |
| 118 |
|
| 119 |
The monitor is executed by sending events to be processed via the functions |
| 120 |
presented below:: |
| 121 |
|
| 122 |
da_handle_event($(event from event enum)); |
| 123 |
da_handle_start_event($(event from event enum)); |
| 124 |
da_handle_start_run_event($(event from event enum)); |
| 125 |
|
| 126 |
The function ``da_handle_event()`` is the regular case where |
| 127 |
the event will be processed if the monitor is processing events. |
| 128 |
|
| 129 |
When a monitor is enabled, it is placed in the initial state of the automata. |
| 130 |
However, the monitor does not know if the system is in the *initial state*. |
| 131 |
|
| 132 |
The ``da_handle_start_event()`` function is used to notify the |
| 133 |
monitor that the system is returning to the initial state, so the monitor can |
| 134 |
start monitoring the next event. |
| 135 |
|
| 136 |
The ``da_handle_start_run_event()`` function is used to notify |
| 137 |
the monitor that the system is known to be in the initial state, so the |
| 138 |
monitor can start monitoring and monitor the current event. |
| 139 |
|
| 140 |
Using the wip model as example, the events "preempt_disable" and |
| 141 |
"sched_waking" should be sent to monitor, respectively, via [2]:: |
| 142 |
|
| 143 |
da_handle_event(preempt_disable_wip); |
| 144 |
da_handle_event(sched_waking_wip); |
| 145 |
|
| 146 |
While the event "preempt_enabled" will use:: |
| 147 |
|
| 148 |
da_handle_start_event(preempt_enable_wip); |
| 149 |
|
| 150 |
To notify the monitor that the system will be returning to the initial state, |
| 151 |
so the system and the monitor should be in sync. |
| 152 |
|
| 153 |
rv/ltl_monitor.h |
| 154 |
++++++++++++++++ |
| 155 |
This file must be combined with the $(MODEL_NAME).h file (generated by `rvgen`) |
| 156 |
to be complete. For example, for the `pagefault` monitor, the `pagefault.c` |
| 157 |
source file must include:: |
| 158 |
|
| 159 |
#include "pagefault.h" |
| 160 |
#include <rv/ltl_monitor.h> |
| 161 |
|
| 162 |
(the skeleton monitor file generated by `rvgen` already does this). |
| 163 |
|
| 164 |
`$(MODEL_NAME).h` (`pagefault.h` in the above example) includes the |
| 165 |
implementation of the Buchi automaton - a non-deterministic state machine that |
| 166 |
verifies the LTL specification. While `rv/ltl_monitor.h` includes the common |
| 167 |
helper functions to interact with the Buchi automaton and to implement an RV |
| 168 |
monitor. An important definition in `$(MODEL_NAME).h` is:: |
| 169 |
|
| 170 |
enum ltl_atom { |
| 171 |
LTL_$(FIRST_ATOMIC_PROPOSITION), |
| 172 |
LTL_$(SECOND_ATOMIC_PROPOSITION), |
| 173 |
... |
| 174 |
LTL_NUM_ATOM |
| 175 |
}; |
| 176 |
|
| 177 |
which is the list of atomic propositions present in the LTL specification |
| 178 |
(prefixed with "LTL\_" to avoid name collision). This `enum` is passed to the |
| 179 |
functions interacting with the Buchi automaton. |
| 180 |
|
| 181 |
While generating code, `rvgen` cannot understand the meaning of the atomic |
| 182 |
propositions. Thus, that task is left for manual work. The recommended practice |
| 183 |
is adding tracepoints to places where the atomic propositions change; and in the |
| 184 |
tracepoints' handlers: the Buchi automaton is executed using:: |
| 185 |
|
| 186 |
void ltl_atom_update(struct task_struct *task, enum ltl_atom atom, bool value) |
| 187 |
|
| 188 |
which tells the Buchi automaton that the atomic proposition `atom` is now |
| 189 |
`value`. The Buchi automaton checks whether the LTL specification is still |
| 190 |
satisfied, and invokes the monitor's error tracepoint and the reactor if |
| 191 |
violation is detected. |
| 192 |
|
| 193 |
Tracepoints and `ltl_atom_update()` should be used whenever possible. However, |
| 194 |
it is sometimes not the most convenient. For some atomic propositions which are |
| 195 |
changed in multiple places in the kernel, it is cumbersome to trace all those |
| 196 |
places. Furthermore, it may not be important that the atomic propositions are |
| 197 |
updated at precise times. For example, considering the following linear temporal |
| 198 |
logic:: |
| 199 |
|
| 200 |
RULE = always (RT imply not PAGEFAULT) |
| 201 |
|
| 202 |
This LTL states that a real-time task does not raise page faults. For this |
| 203 |
specification, it is not important when `RT` changes, as long as it has the |
| 204 |
correct value when `PAGEFAULT` is true. Motivated by this case, another |
| 205 |
function is introduced:: |
| 206 |
|
| 207 |
void ltl_atom_fetch(struct task_struct *task, struct ltl_monitor *mon) |
| 208 |
|
| 209 |
This function is called whenever the Buchi automaton is triggered. Therefore, it |
| 210 |
can be manually implemented to "fetch" `RT`:: |
| 211 |
|
| 212 |
void ltl_atom_fetch(struct task_struct *task, struct ltl_monitor *mon) |
| 213 |
{ |
| 214 |
ltl_atom_set(mon, LTL_RT, rt_task(task)); |
| 215 |
} |
| 216 |
|
| 217 |
Effectively, whenever `PAGEFAULT` is updated with a call to `ltl_atom_update()`, |
| 218 |
`RT` is also fetched. Thus, the LTL specification can be verified without |
| 219 |
tracing `RT` everywhere. |
| 220 |
|
| 221 |
For atomic propositions which act like events, they usually need to be set (or |
| 222 |
cleared) and then immediately cleared (or set). A convenient function is |
| 223 |
provided:: |
| 224 |
|
| 225 |
void ltl_atom_pulse(struct task_struct *task, enum ltl_atom atom, bool value) |
| 226 |
|
| 227 |
which is equivalent to:: |
| 228 |
|
| 229 |
ltl_atom_update(task, atom, value); |
| 230 |
ltl_atom_update(task, atom, !value); |
| 231 |
|
| 232 |
To initialize the atomic propositions, the following function must be |
| 233 |
implemented:: |
| 234 |
|
| 235 |
ltl_atoms_init(struct task_struct *task, struct ltl_monitor *mon, bool task_creation) |
| 236 |
|
| 237 |
This function is called for all running tasks when the monitor is enabled. It is |
| 238 |
also called for new tasks created after the enabling the monitor. It should |
| 239 |
initialize as many atomic propositions as possible, for example:: |
| 240 |
|
| 241 |
void ltl_atom_init(struct task_struct *task, struct ltl_monitor *mon, bool task_creation) |
| 242 |
{ |
| 243 |
ltl_atom_set(mon, LTL_RT, rt_task(task)); |
| 244 |
if (task_creation) |
| 245 |
ltl_atom_set(mon, LTL_PAGEFAULT, false); |
| 246 |
} |
| 247 |
|
| 248 |
Atomic propositions not initialized by `ltl_atom_init()` will stay in the |
| 249 |
unknown state until relevant tracepoints are hit, which can take some time. As |
| 250 |
monitoring for a task cannot be done until all atomic propositions is known for |
| 251 |
the task, the monitor may need some time to start validating tasks which have |
| 252 |
been running before the monitor is enabled. Therefore, it is recommended to |
| 253 |
start the tasks of interest after enabling the monitor. |
| 254 |
|
| 255 |
Final remarks |
| 256 |
------------- |
| 257 |
|
| 258 |
With the monitor synthesis in place using the header files and |
| 259 |
rvgen, the developer's work should be limited to the instrumentation |
| 260 |
of the system, increasing the confidence in the overall approach. |
| 261 |
|
| 262 |
[1] For details about deterministic automata format and the translation |
| 263 |
from one representation to another, see:: |
| 264 |
|
| 265 |
Documentation/trace/rv/deterministic_automata.rst |
| 266 |
|
| 267 |
[2] rvgen appends the monitor's name suffix to the events enums to |
| 268 |
avoid conflicting variables when exporting the global vmlinux.h |
| 269 |
use by BPF programs. |