1. 11 1月, 2011 1 次提交
  2. 02 8月, 2010 1 次提交
    • J
      AppArmor: dfa match engine · e06f75a6
      John Johansen 提交于
      A basic dfa matching engine based off the dfa engine in the Dragon
      Book.  It uses simple row comb compression with a check field.
      
      This allows AppArmor to do pattern matching in linear time, and also
      avoids stack issues that an nfa based engine may have.  The dfa
      engine uses a byte based comparison, with all values being valid.
      Any potential character encoding are handled user side when the dfa
      tables are created.  By convention AppArmor uses \0 to separate two
      dependent path matches since \0 is not a valid path character
      (this is done in the link permission check).
      
      The dfa tables are generated in user space and are verified at load
      time to be internally consistent.
      
      There are several future improvements planned for the dfa engine:
      * The dfa engine may be converted to a hybrid nfa-dfa engine, with
        a fixed size limited stack.  This would allow for size time
        tradeoffs, by inserting limited nfa states to help control
        state explosion that can occur with dfas.
      * The dfa engine may pickup the ability to do limited dynamic
        variable matching, instead of fixing all variables at policy
        load time.
      Signed-off-by: NJohn Johansen <john.johansen@canonical.com>
      Signed-off-by: NJames Morris <jmorris@namei.org>
      e06f75a6