Implementation of 'sct_rules' and its filter expressions

Table Of Contents
  1. Preface
  2. Filter Expressions
    1. What Is A Filter Expression ?
    2. Expressions As Trees
    3. Const Nodes
    4. Variable Reference Nodes
    5. Compound (Operator) Nodes
    6. Filter Expression Vectors
    7. Filter Expression Tree Building
    8. Filter Evaluation
    9. Filter Variables Revisited
      1. Filter Variables Setting And Getting
      2. Filter Variables In The Kernel Module's Code
    10. Filter Expression Serialization And De-Serialization
  3. Rules
    1. What Is A Rule ?
    2. Rule Lists
    3. Rule Matching
    4. Rule Serialization And De-Serialization
  4. Actions

Preface

This doc discusses the implementation of 'sct_rules' - the rule engine and filter expressions library used by the syscall tracker. We will begin with talking about how filter expressions are built and evaluated, talk about the usage of variables inside filter expressions, and then move up to discuss rules, rule lists and rule matching. Finally, we will deal with actions and how they are handled.

This doc assumes the reader is familiar with trees and with tree traversal algorithms, as well as with recursion. Familiarity with expression evaluation in compilers could help too, though is optional.


Filter Expressions

Filter expressions (or just 'filters') are used to store the conditions of rules. Filter expressions are also used to represent constant values that may be stored inside variables.


What Is A Filter Expression ?

A filter expression is actually a tree that represents a logical expression or a mathematical expression. A filter expression may contain operands which are constant values or variable references. Constant values may be of types such as int, short, long, string.

Variable references contain a variable's name (== type), an optional variable's index (if the variable might have several indexed instances) and an optional variable's field index (if the variable contains a vector of values). Note that an indexed variable may have one or more instances containing vectors of values.

Finally, a filter expression may contain operators. Valid operators include mathematical operators (e.g. plus, minus, bitwise and), logical operators (e.g. logical and, logical not) and string operators (substring matching).


Expressions As Trees

A natural method of storing expressions is using trees. Each node in the tree contains a single operand (constant or variable reference) or a single operator. operand nodes are normally leaf nodes, while operator nodes are normally non-leaf nodes. For example, the expression '1 > 2 || 4 + 7' can be stored like this:

        ||
     /      \
    >         +
  /  \       / \
 1    2     4   7


In the code, 'sct_filter_node_t' is a type containing a single filter node. The contents of such a node include the node type (a 'node_type_t' field), the data type of the expression stored in the node and below it (if known; stored as a 'sct_data_type_t' field) and a union whose contents depend on the node type, as will be shown below. Here is the 'sct_filter_node_t' data type, as defined in 'rule_engine_private.h':



/* tracker filter structure. */
struct tracker_filter_node {
  node_type_t type;       /* type of node. */
  sct_data_type_t data_type;  /* data type of node, as inherited. */
                          /* from its contained nodes.        */

  /* varying part of node, depending on 'type'. */
  union {
    struct tracker_filter_node_var var;
    struct tracker_filter_node_const constant;
    struct tracker_filter_node_compound compound;
    struct tracker_filter_node_vector vec;
  } u;
};

Note: One might argue that the given expression ('1 > 2 || 4 + 7') might also be represented, for example, by the following tree:

           >
        /    \
      /        \
   1             ||
               /   \
             2       +
                   /   \
                 4       7
We will see why this is not really the case when we discuss expression evaluation and operator precedence rules later on.


Const Nodes

Const nodes represent constant numeric and string values, such as '1' or 'hello'. Each such node contains a 'type' field with the node's data type, and a union to store the actual node's value, as follows:



/* 'constant' tracker filter node - contains a single constant. */
struct tracker_filter_node_const {
  sct_data_type_t type;       /* type of constant. */
  union {
    int b;               /* bool           */
    char c;              /* char           */
    int i;               /* int            */
    unsigned int ui;     /* unsigned int   */
    long l;              /* long           */
    unsigned long ul;    /* unsigned long  */
    short s;             /* short          */
    unsigned short us;   /* unsigned short */
    float f;             /* float          */
    char* str;           /* string         */
  } u;
};


Variable Reference Nodes

A variable reference node would contain the variable's name, the variable's index and the variable's field index, as follows:



/* 'var' tracker filter node - contains a single variable ref. */
struct tracker_filter_node_var {
  sct_var_type_t type;   /* type of variable.              */
  int var_index;     /* index, if an indexed variable. */
  int field_index;   /* field index, if a var's field. */
};


For variables that have a single instance, 'var_index' will be 0. For variables that do not contain fields, 'field_index' will have the value '-1'.


Compound (Operator) Nodes

Compound nodes (or operator nodes) contain an operator, and pointers to 2 filter nodes. Since some operators are unary (e.g. logical not) sometimes the second filter node pointer will be empty.



/* 'compound' tracker filter node - contains operator and one or more nodes. */
struct tracker_filter_node_compound {
  oper_type_t op;                    /* type of operator.               */
  struct tracker_filter_node* node1; /* first node.                     */
  struct tracker_filter_node* node2; /* second node - binary operators. */
};


'oper_type_t' is an enumeration of operators.


Filter Expression Vectors

Filter nodes may also represent vectors. Vectors are used to represent structures and arrays. Each vector has a size and an array of filter node pointers:



/* 'vector' tracker filter node - contains a vector of filter nodes. */
struct tracker_filter_node_vector {
  int len;                /* length of vector.      */
  sct_filter_node_t** nodes;  /* array of filter nodes. */
};


The Size of a vector is fixed, and is determined when the vector is first created.


Filter Expression Tree Building

filter expression trees are built from the bottom to the top. First we need to build the leaf nodes, then build the operators that bind these leafs, and all the way up to the top. Leaf nodes (containing constants and variable references) are built sing functions as as 'sct_make_int_val', 'sct_make_string_val' and 'sct_make_var_val'. These functions are defined in 'rule_engine_public.h' and implemented in 'filter_node_build.c'. Each such function accepts data for the node, dynamically allocated a filter node, and returns a pointer to that node, or a NULL pointer on failure (e.g. out of memory).

Compound (operator) nodes accept 1 or 2 filter nodes, which are 'swallowed' into a newly allocated filter node. The parameter filter nodes are now owned by the new filter node, and will be freed when this filter node is freed.

Here is a code snippet that builds the tree we have seen earlier, for the '1 > 2 || 4 + 7' expression:


sct_filter_node_t* f_1 = sct_make_int_val(1);
sct_filter_node_t* f_2 = sct_make_int_val(2);
sct_filter_node_t* f_gt = sct_make_greater_then(f_1, f_2);
sct_filter_node_t* f_4 = sct_make_int_val(4);
sct_filter_node_t* f_7 = sct_make_int_val(7);
sct_filter_node_t* f_pl = sct_make_math_plus(f_4, f_7);
sct_filter_node_t* f_or = sct_make_logical_or(f_gt, f_pl);


Note that if a filter node is NULL, trying to use it to build a compound node will fail, returning NULL. Also, if building a filter node fails, then the filter node parameters are also freed, to make sure we don't need to perform complex checking when building a filter expression tree, and to avoid memory leaks. finally, when a filter node is freed, all its contained filter nodes are freed recursively. Thus, all one needs to do is check the final filter node to be non-NULL.


Filter Evaluation

The filter evaluation function, 'sct_eval_filter_node' (declared in 'rule_engine_private.h' and defined in 'filter_eval.c') is the function used to evaluate a filter expression tree. It accepts 2 parameters - a pointer to the root filter node of the tree, and a pointer to a 'const' result filter node, into which the evaluation result will be stored.

The evaluation process itself is done recursively. We take the filter node, and based on its type (const, var, compound) the relevant evaluation function is invoked ('sct_eval_filter_node_const', 'sct_eval_filter_node_var' or 'sct_eval_filter_node_compound').

Evaluating a const node is simply copying the data from the filter node to the result node. Evaluating a variable reference is made of copying the relevant data of the variable (as will be explained below) into the result node.

Evaluating a compound filter node is more complicated. First, we recursively evaluate its first contained filter node, using the 'do_sct_eval_filter_node' function. If there was no error, we handle short-circuiting checks (for logical and as well as for logical or operators). If there is no short-circuiting needed, and we have a binary operator inside the compound node, we recursively evaluate the second contained filter node. Finally we invoke the 'sct_eval_filter_node_op' function to handle the operator itself.

The 'sct_eval_filter_node_op' function is composed of a big switch operation, which invokes the evaluation function for the given operator (functions such as 'eval_op_equal', 'eval_op_greater' or 'eval_op_logic_or'). These functions also make sure that their parameters (operands) are of matching data types, and perform any implicit cast operations required (e.g. if we have an 'int' and a 'short', we cast the 'short' to an 'int' before performing the operation).

Eventually, the result of a filter expression evaluation is an error code (of type 'sct_exp_error_t', defined in 'rules_engine_public.h') and the contents of the 'result' filter node. We need to make sure that the error code is 'ERR_NONE', in order to know that the result node contains a valid value.

As you can see, the manner in which operands our bound to operators is determined by the structure of the tree. Thus, if we have a '1 > 2 + 3' expression, we should have '>' in the root node, and not '+' there, so the evaluation will be made according to normal operator precedence rules, as used in the C programming language - '+' takes precedence over '>', and so we will calculate '2 + 3' first, and only then compare '1' to the result, using the '>' operator.


Filter Variables Revisited

Lets say a few more words about variables. Basically, variables are used to store some temporary data at one point, to be used at a later point.


Filter Variables Setting And Getting

You can set a value for a variable using the 'set_var', 'set_var_field' or 'set_var_indexed' functions (declared in 'filter_vars_public.h' defined in 'filter_vars.c'). The value of a variable should be either a constant expression, or a vector of constant expressions. Just like when building compound filter nodes, the filter node value is 'swallowed' and thus owned by the variable. When the variable's value is reset (by a call to 'reset_all_vars') or gets assigned to again, the old filter node value is being freed.

Later on, we can get the value of a variable, by invoking 'get_var' or 'get_var_indexed'. This will return a pointer to a filter node, containing the variable's contents.

Filter Variables In The Kernel Module's Code

So how does the kernel module use variables? the answer is, that variables are being reset and then having their value set every time a system call is invoked. System call parameters are stored into the VT_PARAMS indexed variable; Process state information (UID, PID, GID...) is stored in VT_PROC_UID, VT_PROC_PID and VT_PROC_GID variables; etc.

After the variables have been set, filter expressions stored inside filtering rules (to be discussed below) are evaluated, and this is where variable references come to life, by extracting the data previously stored in the variables.


Filter Expression Serialization And De-Serialization

In order to allow user-mode applications and kernel module code to exchange filter expressions, we need a method to encode a filter expression inside a buffer, and a method to decode a filter expression from a buffer, building a new tree to store the expression.

Encoding and decoding is first applied to primitive types. Using 'memcpy' calls, we can copy the contents of a primitive type (e.g. int, short, long) into a given location in a buffer. This is done using functions such as 'encode_int' and 'encode_long' (declared in 'encode_decode_public.h', defined in 'encode_decode.c').

Decoding basic types is done by copying data (again, using 'memcpy') from a buffer into a C language variable (e.g. int, short, long), using functions such as 'decode_int' and 'decode_long'.

The string type is encoded by the 'encode_string' function. Since a string has a length, and a character array, it is encoded as an int (defining its length) followed by a copy of the strings, without the null character. Decoding the string is done in the reverse order - we extract the string's size (an int), allocated a memory chunk whose length is the decoded size plus one (for the null character) and then copy the string's contents from the buffer to the newly allocated memory chunk.

Finally, encoding a filter node will constitute of encoding the filter node's type and its data type, followed by encoding the data specific to that of the filter node. All this is done by the 'sct_serialize_filter_node' function (declared in 'rule_engine_public.h', defined in 'filter_in_out.c'). Decode of a filter node is done using the 'sct_desct_serialize_filter_node' function.


Rules

Rules are the top-level objects of the sct_rules library. They allow defining conditional expressions (filters) and actions to be taken if the conditions evaluate to 'true'.


What Is A Rule ?

A rule is made of a rule id (a number), a filter expression and an action. When a rule is tested, its filter expression is evaluated, in a given context specified by variables of the rules library, as was explained previously. If the filter expression evaluates to 'true', the rule's action is performed. In the code, a rule is stored in a structure defined in 'rule_engine_private.h':



/* tracker rule structure. */
struct tracker_rule {
  int rule_id;
  struct tracker_filter_node* filter;
  struct tracker_action action;
};


Rule Lists

Rules are usually stored in lists. A newly created list of rules is empty (i.e. contains no rules) initially. rules may be added to the rules list by the function 'sct_add_tracking_rule' (declared in 'rule_engine_public.h', defined in 'rule_engine.c'), and removed from the list by the function sct_del_tracking_rule. The list is internally represented as a fixed-size vector, for simplicity. Rules are ordered in the list according to their rule id, smallest ID first, largest ID last. In the code, rule lists are stored in a structure defined in 'rule_engine.c':



/* a list of tracking rules. */
#define MAX_NUM_TRACKER_RULES   20

struct rule_list {
  struct tracker_rule* rules[MAX_NUM_TRACKER_RULES];
  int num_rules;
};


Rule Matching

Rule matching is handled by the 'sct_filter_syscall' function (declared in 'rule_engine_public.h', defined in 'rule_engine.c'). It accepts a rule list, a system call ID and a variable arguments list, containing the parameters of the system call. The function then tries to test the rules of the list one by one, according to their order in the list. When the filter expression of a rule evaluates to 'true', the rule is said to match. In such a case, the rule's action is performed, and the 'sct_filter_syscall' function returns. Thus, the first rule that matches a syscall invocation terminates the rule matching operation.


Rule Serialization And De-Serialization

In order to pass rules from user programs into the kernel (and vice versa), rules can be serialized into a byte array, and de-serialized from this byte array. Rule serialization is done by serializing each part of the rule (i.e. rule Id, rule's filter expression and rule's action). In fact, the serialization also contains the system call ID, as it is not stored inside the rule normally - this is needed so the kernel knows which system call the rule should be applied to - rule lists are stored per system-call. In the code. rule serialization is done using the 'sct_serialize_tracking_rule' function (declared in 'rule_engine_public.h', defined in 'rule_engine.c'). Rule de-serialization is done using the 'sct_desct_serialize_tracking_rule' function.


Actions

Actions are used to decide what to do once a rule matches a given system call invocation. Currently, actions are stored inside a structure defined in 'rule_engine_private.h':



/* tracker action structure. */
struct tracker_action {
        sct_action_type_t type;
        union {
                int priority;   /* priority for message logging.      */
                int rule_id;    /* rule ID to be enabled/disabled.    */
                int error_code; /* error code when failing a syscall. */
        } u;
};


The action has a type (e.g. AT_LOG, AT_RULE_ENABLE), and then a union, containing data that varies, depending on the action's type. The only action type currently supported is AT_LOG.

Actions are performed using the 'sct_tracker_perform_action' function (declared in 'rule_engine_public.h', defined in 'rule_engine.c'). This function accepts a rules list, an action, a system call ID, a syscalls parameters specifier string, and a varying number of syscall parameters.

The only interesting part is the parameter specifier. This is a string that specifies the types of the parameters the syscall received, in a manner similar to that of the format specified of 'printf'. For example, 's' refers to a 'string' parameter, 'h' to a 'short', 'ui' to an 'unsigned int', etc. The number of parameters is determined by the number of type specifiers.

Note: Since the 'actions' part of the code is not quite mature yet, it is bound to change considerably in the future.