{"id":279,"date":"2015-02-22T10:50:40","date_gmt":"2015-02-22T10:50:40","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdoc\/?page_id=279"},"modified":"2017-03-28T16:01:32","modified_gmt":"2017-03-28T16:01:32","slug":"the-orchids-language","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/orchidsdoc\/?page_id=279","title":{"rendered":"The Orchids language"},"content":{"rendered":"

Orchids works by detecting patterns, possibly quite complex, in flows of incoming events.\u00a0 Those patterns are described in rules, typically loaded by the $OCONF\/orchids-rules.conf<\/code> configuration file. In turn, those rules must be written in the Orchids language, described below.<\/p>\n

Example<\/h2>\n

A typical example of a rule would be the following, known as the pid tracker ($OCONF\/rules\/pid_tracker_audit.rule<\/code>):<\/p>\n

#include \"linux64syscall.h\"\r\n\r\nrule pidtrack synchronize($pid)\r\n{\r\n  state init\r\n  {\r\n    expect (.auditd.syscall==SYS_clone ||\r\n\t    .auditd.syscall==SYS_fork ||\r\n\t    .auditd.syscall==SYS_vfork)\r\n      goto newpid;\r\n  }\r\n\r\n  state newpid! {\r\n    $pid = .auditd.exit;\r\n    $uid = .auditd.euid;\r\n    $gid = .auditd.egid;\r\n\r\n    case ($uid==0) goto end; \/* everything root does is OK *\/\r\n    else goto wait;\r\n  }\r\n\r\n  state wait!\r\n  {\r\n    expect (.auditd.pid == $pid &&\r\n\t    .auditd.syscall == SYS_execve &&\r\n\t    (.auditd.uid != .auditd.euid || .auditd.gid != .auditd.egid) && \/* hack *\/\r\n\t    .auditd.success == \"yes\")\r\n      goto update_uid_gid;\r\n\r\n    expect (.auditd.pid == $pid &&\r\n\t    (.auditd.syscall == SYS_setresuid ||\r\n\t     .auditd.syscall == SYS_setreuid ||\r\n\t     .auditd.syscall == SYS_setuid) &&\r\n\t    .auditd.success == \"yes\")\r\n      goto update_setuid;\r\n\r\n    expect (.auditd.pid == $pid &&\r\n\t    (.auditd.syscall == SYS_setresgid ||\r\n\t     .auditd.syscall == SYS_setregid ||\r\n\t     .auditd.syscall == SYS_setgid) &&\r\n\t    .auditd.success == \"yes\")\r\n      goto update_setgid;\r\n\r\n    expect (.auditd.pid == $pid &&\r\n\t    .auditd.syscall == SYS_exit)\r\n      goto end;\r\n\r\n    expect (.auditd.syscall == SYS_kill &&\r\n\t    .auditd.a0 == $pid &&\r\n\t    .auditd.a1 == 9)\r\n      goto end;\r\n\r\n    expect (.auditd.pid == $pid &&\r\n\t    (.auditd.euid != $uid || .auditd.egid != $gid))\r\n      goto alert;\r\n  }\r\n\r\n  state update_uid_gid!\r\n  {\r\n    $uid = .auditd.euid;\r\n    $gid = .auditd.egid;\r\n\r\n    case ($uid==0) goto end; \/* everything root does is OK *\/\r\n    else goto wait;\r\n  }\r\n\r\n  state update_setuid!\r\n  {\r\n    case (.auditd.egid != $gid) goto alert;\r\n    else goto update_uid_gid;\r\n  }\r\n\r\n  state update_setgid!\r\n  {\r\n    case (.auditd.euid != $uid) goto alert;\r\n    else goto update_uid_gid;\r\n  }\r\n\r\n  state alert!\r\n  {\r\n    $newuid = .auditd.euid;\r\n    $newgid = .auditd.egid;\r\n    print_string (\"Alert report :\\n\");\r\n\r\n    print_string (\"Privilege escalation by uid=\");\r\n    print_string (str_from_uint($uid));\r\n    print_string (\", now \");\r\n    print_string (str_from_uint($newuid));\r\n    print_string (\", gid=\");\r\n    print_string (str_from_uint($gid));\r\n    print_string (\", now \");\r\n    print_string (str_from_uint($newgid));\r\n    print_string (\", pid=\");\r\n    print_string (str_from_uint($pid));\r\n    print_string (\"\\n\");\r\n    report();\r\n  }\r\n\r\n  state end!\r\n  {\r\n    \/* all went well *\/\r\n  }\r\n}\r\n<\/pre>\n
This reads, roughly, as follows.\u00a0 We assume that Orchids reads from a source of events provided by the Linux auditd daemon, configured thanks to the auditd module<\/a>.\u00a0 Each new event received will have Orchids launch a new thread for rule pidtrack<\/code>, starting at state init<\/code>. This expects to see a Linux system call that creates a new process.<\/p>\n
Once such an Orchids thread has found one, it goes to state newpid<\/code>. There is stores the pid of the created process, which happens to be the exit code .auditd.exit<\/code> of the fork or clone primitive, into a local variable $pid<\/code>. It also stores the current effective user id and group id into appropriate variables. If the effective user id is not root, it then goes to the main state of that rule, wait<\/code>.<\/p>\n
When in the wait<\/code> state, the Orchids thread will wait upon one of 6 possible kinds of events, each described by an expect<\/code> clause. For example, the first one expects the monitored process (with pid stored in $pid<\/code>) to call the Linux primitive execve()<\/code> with a modified effective user id or a modified group id. This is legitimate, and happens in case we execute processes with the setuid or setgid bit set. If that happens, that thread will go to state update_uid_gid<\/code>, which will update the values of the variables $uid<\/code> and $gid<\/code> that hold our current view of what the current effective user id and group id of process $pid<\/code> are.<\/p>\n
The next 4 expect<\/code> clauses describe other legitimate cases where the effective user id or the group id of process $pid<\/code> changes.<\/p>\n
The final expect<\/code> clause detects cases where a system call has been made with unexpected effective user id or group id. In that case, the Orchids thread goes to state alert<\/code>, which prints a message and calls report()<\/code> to produce alert reports in a variety of formats.<\/p>\n
If\u00a0 a state, such as wait<\/code>, has several expect<\/code> clauses, then it will wait on all<\/em> of them.\u00a0 The most effective way to understand what it does is to imagine that Orchids will fork as many subthreads as there are expect<\/code> clauses, each one waiting on an event satisfying the boolean condition immediately following the expect<\/code> keyword.\u00a0\u00a0 Once one is found, the Orchids thread goes to the state mentioned after the goto<\/code> keyword.<\/p>\n
States marked with a !<\/code> sign are commit<\/em> states.\u00a0 When you enter such a state, all the other subthreads waiting on alternative expect<\/code> conditions are killed, and only the current one is kept.\u00a0 Let us be more precise.\u00a0 Each thread takes part in a thread group<\/em>.\u00a0 For each new event read, for each rule whose first state expects a condition that matches that event, a new thread group is created, with just one thread in it.\u00a0 When a thread reaches a state with multiple expect<\/code> clauses, it forks as many subthreads as there are expect<\/code> clauses.\u00a0 Those subthreads are in the same thread group as the parent thread.\u00a0\u00a0 (As a special case, any state with no expect<\/code> will simply fork no subthread, and terminate.\u00a0 This is what states alert<\/code> and end<\/code> do.) When a thread reaches a commit state, it first kills all the other threads that are in the same thread group: it commits<\/em> to the path of events that it has just found, and disregards all other candidate paths.<\/p>\n
Finally, our example rule exhibits another peculiar feature: the synchronized($pid)<\/code> phrase after the rule name, right at the beginning. That instructs Orchids to only keep one thread group, among all with the same rule, whose threads will have the same value of $pid<\/code>. In other words, imagine Orchids starts monitoring events through the pidtrack<\/code> rule and discovers that $pid<\/code> should be set to, say, 102 (when it sets it, in state newpid<\/code>).\u00a0 Imagine it already had an active thread group that already monitors pid number 102.\u00a0 Then Orchids will kill the newer thread group, and only keep the older one.<\/p>\n
Syntax<\/h2>\n
The grammar of the Orchids language is given in Backus-Naur Form<\/a>, with some standard extensions.\u00a0 Tokens are given in typewriter script between single quotes, e.g., ‘rule<\/code>‘.\u00a0 Productions are given in italic, e.g., rule<\/em>.\u00a0 A star means repetition of zero, one or more items, while a plus sign means repetition of one of more items.\u00a0 Parenthesis are used to group symbols or productions.\u00a0 Square brackets denote optional sequences.<\/p>\n
Grammar<\/h3>\n
orchids-file<\/em> ::= rule<\/em>*<\/p>\n
rule<\/em> ::= ‘rule<\/code>‘ SYMNAME [‘synchronize<\/code>‘\u00a0 ‘(<\/code>‘\u00a0 sync_var_list<\/em>\u00a0 ‘)<\/code>‘ ]\u00a0\u00a0 ‘{<\/code>‘\u00a0 state<\/em>+<\/sup>\u00a0 ‘}<\/code>‘<\/p>\n
sync_var_list<\/em> ::= VARIABLE (‘,<\/code>‘ VARIABLE)*<\/p>\n
state<\/em> ::= ‘state<\/code>‘ SYMNAME ‘ state_option*\u00a0<\/em>{<\/code>‘\u00a0 statement<\/a>* actions<\/em>\u00a0‘}<\/code>‘<\/p>\n
state_option<\/em>\u00a0::= \u00a0‘!<\/code>‘<\/p>\n
statement<\/em><\/a> ::= expr<\/a> ‘;<\/code>‘ <\/em>| conditional <\/em>| split-regexp<\/em>
\nconditional<\/em> ::= ‘if<\/code>‘ expr<\/em><\/a> ‘then<\/code>‘ statement<\/em><\/a> [‘else<\/code>‘ statement<\/em><\/a>] ‘;<\/code>‘
\nsplit-regexp<\/em> ::= ‘split<\/code>‘ STRING ‘\/<\/code>‘ optional_var_list<\/em> ‘\/<\/code>‘ expr<\/em> ‘;<\/code>‘<\/p>\n
actions<\/em> ::=\u00a0transition<\/em>* | cases<\/em><\/p>\n
optional_var_list<\/em> ::=
\n| VARIABLE (‘,<\/code>‘ VARIABLE)*<\/p>\n
transition<\/em> ::=
\n‘expect<\/code>‘ ‘(<\/code>‘ expr<\/em><\/a> ‘)<\/code>‘ ‘goto<\/code>‘ SYMNAME
\n| ‘expect<\/code>‘ ‘(<\/code>‘ expr<\/em><\/a> ‘)<\/code>‘ ‘{<\/code>‘ statement<\/a>* actions<\/em>\u00a0‘}<\/code>‘<\/p>\n
cases<\/em>\u00a0::= [‘case<\/code>‘\u00a0‘(<\/code>‘\u00a0expr<\/em><\/a>\u00a0‘)<\/code>‘\u00a0‘goto<\/code>‘ SYMNAME ‘;<\/code>‘\u00a0‘else<\/code>‘]*\u00a0‘goto<\/code>‘ SYMNAME<\/p>\n
Tokens<\/h3>\n
SYMNAME:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 \u00a0\u00a0 [<\/code>a<\/code>–z_<\/code>][A<\/code>–Za<\/code>–z0<\/code>–9_.<\/code>]*
\nused for rule names, state names, function names<\/p>\n
VARIABLE:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 $<\/code>[A<\/code>–Za<\/code>–z_<\/code>][A<\/code>–Za<\/code>–z0<\/code>–9_.<\/code>]*
\nvariable names; note that they start with ‘$<\/code>‘<\/p>\n
LOGICAL:\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 [A<\/code>–Z<\/code>][A<\/code>–Za<\/code>–z0<\/code>–9_.<\/code>]*
\nlogical variable names, as used in database comprehensions; can also be used just like variables, but cannot be assigned to<\/p>\n
STRING:
\nstring constant, enclosed in double quotes, as in C<\/p>\n