Debian Codegraph @

Documentation/trace/rv/linear_temporal_logic.rst

raw
1 Linear temporal logic
2 =====================
3
4 Introduction
5 ------------
6
7 Runtime verification monitor is a verification technique which checks that the
8 kernel follows a specification. It does so by using tracepoints to monitor the
9 kernel's execution trace, and verifying that the execution trace sastifies the
10 specification.
11
12 Initially, the specification can only be written in the form of deterministic
13 automaton (DA). However, while attempting to implement DA monitors for some
14 complex specifications, deterministic automaton is found to be inappropriate as
15 the specification language. The automaton is complicated, hard to understand,
16 and error-prone.
17
18 Thus, RV monitors based on linear temporal logic (LTL) are introduced. This type
19 of monitor uses LTL as specification instead of DA. For some cases, writing the
20 specification as LTL is more concise and intuitive.
21
22 Many materials explain LTL in details. One book is::
23
24 Christel Baier and Joost-Pieter Katoen: Principles of Model Checking, The MIT
25 Press, 2008.
26
27 Grammar
28 -------
29
30 Unlike some existing syntax, kernel's implementation of LTL is more verbose.
31 This is motivated by considering that the people who read the LTL specifications
32 may not be well-versed in LTL.
33
34 Grammar:
35 ltl ::= opd | ( ltl ) | ltl binop ltl | unop ltl
36
37 Operands (opd):
38 true, false, user-defined names consisting of upper-case characters, digits,
39 and underscore.
40
41 Unary Operators (unop):
42 always
43 eventually
44 next
45 not
46
47 Binary Operators (binop):
48 until
49 and
50 or
51 imply
52 equivalent
53
54 This grammar is ambiguous: operator precedence is not defined. Parentheses must
55 be used.
56
57 Example linear temporal logic
58 -----------------------------
59 .. code-block::
60
61 RAIN imply (GO_OUTSIDE imply HAVE_UMBRELLA)
62
63 means: if it is raining, going outside means having an umbrella.
64
65 .. code-block::
66
67 RAIN imply (WET until not RAIN)
68
69 means: if it is raining, it is going to be wet until the rain stops.
70
71 .. code-block::
72
73 RAIN imply eventually not RAIN
74
75 means: if it is raining, rain will eventually stop.
76
77 The above examples are referring to the current time instance only. For kernel
78 verification, the `always` operator is usually desirable, to specify that
79 something is always true at the present and for all future. For example::
80
81 always (RAIN imply eventually not RAIN)
82
83 means: *all* rain eventually stops.
84
85 In the above examples, `RAIN`, `GO_OUTSIDE`, `HAVE_UMBRELLA` and `WET` are the
86 "atomic propositions".
87
88 Monitor synthesis
89 -----------------
90
91 To synthesize an LTL into a kernel monitor, the `rvgen` tool can be used:
92 `tools/verification/rvgen`. The specification needs to be provided as a file,
93 and it must have a "RULE = LTL" assignment. For example::
94
95 RULE = always (ACQUIRE imply ((not KILLED and not CRASHED) until RELEASE))
96
97 which says: if `ACQUIRE`, then `RELEASE` must happen before `KILLED` or
98 `CRASHED`.
99
100 The LTL can be broken down using sub-expressions. The above is equivalent to:
101
102 .. code-block::
103
104 RULE = always (ACQUIRE imply (ALIVE until RELEASE))
105 ALIVE = not KILLED and not CRASHED
106
107 From this specification, `rvgen` generates the C implementation of a Buchi
108 automaton - a non-deterministic state machine which checks the satisfiability of
109 the LTL. See Documentation/trace/rv/monitor_synthesis.rst for details on using
110 `rvgen`.
111
112 References
113 ----------
114
115 One book covering model checking and linear temporal logic is::
116
117 Christel Baier and Joost-Pieter Katoen: Principles of Model Checking, The MIT
118 Press, 2008.
119
120 For an example of using linear temporal logic in software testing, see::
121
122 Ruijie Meng, Zhen Dong, Jialin Li, Ivan Beschastnikh, and Abhik Roychoudhury.
123 2022. Linear-time temporal logic guided greybox fuzzing. In Proceedings of the
124 44th International Conference on Software Engineering (ICSE '22). Association
125 for Computing Machinery, New York, NY, USA, 1343–1355.
126 https://doi.org/10.1145/3510003.3510082
127
128 The kernel's LTL monitor implementation is based on::
129
130 Gerth, R., Peled, D., Vardi, M.Y., Wolper, P. (1996). Simple On-the-fly
131 Automatic Verification of Linear Temporal Logic. In: Dembiński, P., Średniawa,
132 M. (eds) Protocol Specification, Testing and Verification XV. PSTV 1995. IFIP
133 Advances in Information and Communication Technology. Springer, Boston, MA.
134 https://doi.org/10.1007/978-0-387-34892-6_1