[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Alternative way to constrain the use of string
"FPDS" (stands for "Following Pattern Distinguished String" is the key concept of detecting string/data abuse. first, define three state type fpdsType. fpdsType can be either "no", "string" or "anyString". * OR operation (commutative) "no"||"no" -> "no" "string"||"string" -> "string" "anyStr"||"anyStr" -> "anyStr" "string"|| X -> "string" "anyStr"|| "no" -> "anyStr" The algorithm consists of two procedures. Procedure "check" detects if the given pattern abuses string/data. Procedure "calcFPDS" computes if the given pattern can start with string/data/anyString. The check process starts by check( topLevelPattern, "no" ). algorithm: check detects abuse of string/data. input: $pattern : TREX pattern $fpds : fpdsType output: nothing if($pattern is "<string>e</string>" or "<data>e</data>" and $fpds="string","anyStr") this pattern is illegal. if($pattern is "<group>p1 p2</group>") check( p2, $fpds ) check( p1, calcFPDS(p2,$fpds) ) if($pattern is "<oneOrMore> p1 </oneOrMore>") check( p1, $fpds || calcFPDS(p1,$fpds) ) if($pattern is "<interleave> p1 p2 ... pn </interleave>") for i=1 to n do $fpds |= calcFPDS(pi,false) next for i=1 to n do check( pi, $fpds ) next if($pattern is "<choice> p1 p2 </choice>") check( p1, $fpds ) check( p2, $fpds ) if($pattern is "<anyString />" and $fpds=="string") this pattern is illegal. if($pattern is "<attribute>p</attribute>" or "<element>p</element>") check( p, "no" ) exit function. ------------------------------------------------------------------ algorithm: calcFPDS computes if the given pattern can start with string literal. input: $pattern : TREX pattern $fpds : fpdsType output: fpdsType if($pattern is "<string>e</string>" or "<data>e</data>" and $fpds=true) return "string" if($pattern is "<group>p1 p2</group>") return calcFPDS(p1, calcFPDS(p2,$fpds)) if($pattern is "<oneOrMore> p1 </oneOrMore>") return calcFPDS(p1,$fpds) if($pattern is "<interleave> p1 p2 </interleave>") return calcFPDS(p1,$fpds)||calcFPDS(p2,$fpds) if($pattern is "<choice> p1 p2 </choice>") return calcFPDS(p1,$fpds)||calcFPDS(p2,$fpds) if($pattern is "<anyString />") return "anyStr" if($pattern is "<attribute />" or "<element />") return "no" exit function. ---- Kohsuke KAWAGUCHI Phone: 650-786-0721
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC