[Aide] manual.html, Understanding Aide rule matching

Marc Haber mh+aide at zugschlus.de
Sun Dec 18 20:02:33 EET 2005 

On Sun, Dec 18, 2005 at 06:53:21PM +0100, Marc Haber wrote:
> See the attached patch against current aide CVS for documentation
> optimization.

And here is the same diff in unified format. Sorry for forgetting the
"-u" and not verifying the patch.

Greetings
Marc

-- 
-----------------------------------------------------------------------------
Marc Haber         | "I don't trust Computers. They | Mailadresse im Header
Mannheim, Germany  |  lose things."    Winona Ryder | Fon: *49 621 72739834
Nordisch by Nature |  How to make an American Quilt | Fax: *49 621 72739835
-------------- next part --------------
Index: doc/aide.conf.5.in
===================================================================
RCS file: /cvsroot/aide/aide/doc/aide.conf.5.in,v
retrieving revision 1.4
diff -u -r1.4 aide.conf.5.in
--- doc/aide.conf.5.in	15 Nov 2005 16:17:11 -0000	1.4
+++ doc/aide.conf.5.in	18 Dec 2005 18:01:13 -0000
@@ -17,10 +17,10 @@
 .PP
 There are three types of lines in \fBaide.conf\fP. First there are the
 configuration lines which are used to set configuration parameters and
-define/undefine variables. Second, there are lines that used to select
-which files are added to the database. Third there are the macrolines.
-Only the second type of lines are required for aide to do anything.
-Lines beginning with # are ignored as comments.
+define/undefine variables. Second, there are selection lines that are used
+to indicate which files are added to the database. Third, macro lines 
+define or undefine variables within the config file. Lines beginning
+with # are ignored as comments.
 .PP
 .SH "CONFIG LINES"
 .PP
@@ -78,20 +78,22 @@
 Note that this is different from the way Tripwire(tm) does it.
 .IP
 There is also a special group named "ignore_list". The predefined 
-groups listed in it are NOT displayed in the final report.
+-groups listed in it are NOT displayed in the final report.
 .PP
 .SH "SELECTION LINES"
 .PP
-There are three types of selection lines (regular, negative, equals)
-Lines beginning with "/" are regular selective lines. Lines beginning
-with "!" are negative selection lines. And lines beginning with "="
-are equals selection lines. The string following the first character
-is taken as a regular expression matching to a complete filename (with
-path included). In regular selection rule the "/" is included in the
-regular expression. Following the regular expression in an expression.
-See CONFIG LINES for an explanation of exressions. See EXAMPLES and 
-doc/aide.conf for examples.
-
+aide supports three types of selection lines (regular, negative, equals)
+Lines beginning with "/" are regular selection lines. Lines beginning
+with "=" are equals selection lines. And lines beginning with "!"
+are negative selection lines. The string following the first character
+is taken as a regular expression matching to a complete filename,
+including the path. In a regular selection rule the "/" is included in the
+regular expression. Following the regular expression is a group
+definition as explained above. See EXAMPLES and doc/aide.conf for examples.
+.PP
+More in-depth discussion of the selection algorithm can be found in
+the aide manual.
+.IP
 .PP
 .SH "MACRO LINES"
 .PP
Index: doc/manual.html
===================================================================
RCS file: /cvsroot/aide/aide/doc/manual.html,v
retrieving revision 1.1.1.1
diff -u -r1.1.1.1 manual.html
--- doc/manual.html	16 Jan 2003 10:37:34 -0000	1.1.1.1
+++ doc/manual.html	18 Dec 2005 18:01:14 -0000
@@ -145,8 +145,7 @@
 <h2>Configuration</h2>
 <p>
 Next you have to create a configuration file. You can find
-documentation for this in aide.conf(5) manual page. Here are a few
-pointers for what to look for.
+more documentation for this in aide.conf(5) manual page.
 </p>
 <p>
 There are three types of lines in aide.conf:
@@ -260,35 +259,67 @@
 but it is worth it.
 </p>
 <p>
-In the initialisation process Aide creates a tree of the regexp
-rules. Each type of rule is placed in a separate list for each node in
-the tree. So we have an equals rule list,a select rule list and a
-negative selection rule list for all nodes. These lists may be empty.
-The node in which a rule is placed is determined by the first special
-regexp character in the rule. For example <code>!/proc</code> would be
-placed in the root node. While <code>!/proc/.*</code> would be placed
-in /proc node. Also in front of each rule Aide adds an implicit ^.
+As you already know, aide has three types of selection lines:
+<ul>
+<li>Regular selection lines, beginning with "/".</li>
+<li>Equals selection lines, beginning with "=".</li>
+<li>Negative selection lines, beginning with "!".</li>
+</ul>
+The string following the first character is taken as a regular
+expression matching to a complete filename, including the path. In a
+regular selection rule, the slash is included in the regular
+expression. An implicit ^ is added in front of each rule. A group
+definition follows the regular expression.
+</p>
+<p>
+When reading the configuration file, aide internally builds a tree
+that roughly resembles the directory tree to be checked. Each node
+corresponds to a directory, and each node has one rule list for the
+associated regular selection lines, one for the associated negative
+selection lines and one for the associated equals selection lines. If
+there is no associated rule, the respective list may be empty.
+</p>
+<p>
+aide tries to place a rule as far down in the tree as possible while
+still assuring that it is above all files that it matches. This is
+determined by the first "special" regexp character in the rule. For
+example, <code>!/proc</code> would be placed in the root node,
+<code>!/proc/.*</code> would be placed in the /proc node,
+<code>!/var/log/syslog*</code> is placed in the /var/log node and,
+finally, <code>!/home/[a-z0-9]+/.bashrc$</code> is placed in the /home
+node.
 </p>
 <p>
-When Aide does rule matching it uses the following algorithm.
-The following is a pseudocode adaptation from src/gen_list.c.
+The algorithm that aide uses for rule matching is described in the
+following paragraphs. The pseudocode is an adaption from src/gen_list.c.
 <code>
 <pre>
-check_node_for_match(node,filename)
-	if(no deeper match found)
-		check(equals list for this node)
-
-	if(no deeper match found)
-		check(select list for this node)
-
-	check_node_for_match(nodes parent,filename)
-
-	if(this file is about to be added)
-		check(negative select list for this node) 
-	
+check_node_for_match(node,filename,first_time)
+	if (first_time)
+        	check(equals list for this node)
+
+	check(regular list for this node)
+
+	if (node is not the root node)
+		check_node_for_match(nodes parent,filename,false)
+
+	if (this file is about to be added)
+		check(negative list for this node)
+
 	return (info about whether this file should be added or not and how)
 </pre>
 </code>
+When aide needs to determine whether a file found in the file system is
+to be checked, it first determines the deepest possible node x to
+match the current file against (that algorithm is not part of the
+pseudocode above), and then calls check-node_for_match(x, filename,
+true). So, the recursion starts at the deepest possible match.
+</p>
+<p>
+As it can also be seen, equals selection lines are only checked in the
+first recursion step, thus providing some kind of speed optimization
+by reducing the number of necessary regular expression evaluations,
+which is a quite expensive operation.
 </p>
 <h5>Pitfalls</h5>
 <p>

More information about the Aide mailing list