16 March 2016

Catastrophic Backtracking

RegExp Playground

This repository contains several regexp examples.

Examples

1. Catastrophic Backtracking

This is Java example of backtracking catastrophic shown in Coding Horror post This is a known behavior when using nesting repetition operators, that has been analyzed in stackoverlow, regular expressions dedicated sites.
It can be seen the exponential explosion that take to parse using regexp for a simple pattern:
(x+x+)y+
Details of this issue can be found on the above links.

Execute

mvn clean package
mvn exec:java -Dexec.mainClass="cl.devweb.regexp.exploit.CatastrophicBacktracking"

Rule of Thumb - Solution

The solution is simple. When nesting repetition operators, make absolutely sure that there is only one way to match the same match. If repeating the inner loop 4 times and the outer loop 7 times results in the same overall match as repeating the inner loop 6 times and the outer loop 2 times, you can be sure that the regex engine will try all those combinations.

OUTPUT

 mvn exec:java -Dexec.mainClass="cl.devweb.regexp.exploit.CatastrophicBacktracking"
[INFO] Scanning for projects...
[INFO]                                                                         
[INFO] ------------------------------------------------------------------------
[INFO] Building regexp-exploit 0.0.1-SNAPSHOT
[INFO] ------------------------------------------------------------------------
[INFO] 
[INFO] --- exec-maven-plugin:1.4.0:java (default-cli) @ regexp-exploit ---
Found value: xxxxxxxxxxxxxy  timer=113.2 μs
Invalid match of 1 chars took 20.97 μs
Invalid match of 2 chars took 14.28 μs
Invalid match of 3 chars took 21.82 μs
Invalid match of 4 chars took 149.2 μs
Invalid match of 5 chars took 26.92 μs
Invalid match of 6 chars took 43.73 μs
Invalid match of 7 chars took 80.80 μs
Invalid match of 8 chars took 135.6 μs
Invalid match of 9 chars took 207.1 μs
Invalid match of 10 chars took 240.6 μs
Invalid match of 11 chars took 442.9 μs
Invalid match of 12 chars took 848.0 μs
Invalid match of 13 chars took 1.623 ms
Invalid match of 14 chars took 2.504 ms
Invalid match of 15 chars took 4.339 ms
Invalid match of 16 chars took 8.163 ms
Invalid match of 17 chars took 16.60 ms
Invalid match of 18 chars took 33.27 ms
Invalid match of 19 chars took 69.98 ms
Invalid match of 20 chars took 138.2 ms
Invalid match of 21 chars took 268.9 ms
Invalid match of 22 chars took 537.9 ms
Invalid match of 23 chars took 977.8 ms
Invalid match of 24 chars took 2.132 s
Invalid match of 25 chars took 4.260 s
Invalid match of 26 chars took 8.433 s
Invalid match of 27 chars took 17.18 s
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 34.977 s
[INFO] Finished at: 2016-03-16T12:38:59-03:00
[INFO] Final Memory: 9M/245M
[INFO] ------------------------------------------------------------------------
We can see taking a Thread Dump, where is spending (wasting?) most of the time:
"main" #1 prio=5 os_prio=31 tid=0x00007f8f9a006000 nid=0x1303 runnable [0x000000010a718000]
   java.lang.Thread.State: RUNNABLE
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4785)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4717)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4785)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4717)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4785)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4717)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4785)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4717)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4785)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4717)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4785)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4717)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4785)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4717)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4272)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4234)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4658)
    at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4801)
    at java.util.regex.Pattern$Prolog.match(Pattern.java:4741)
    at java.util.regex.Pattern$Start.match(Pattern.java:3461)
    at java.util.regex.Matcher.search(Matcher.java:1248)
    at java.util.regex.Matcher.find(Matcher.java:637)
    at cl.devweb.regexp.exploit.CatastrophicBacktracking.main(CatastrophicBacktracking.java:81)

TODO

  • add more examples :)

License

MIT . .

15 March 2016

Maven Cheat Sheet

Some reminder for Maven:

1. Use a different settings.xml
mvn --settings ~/.m2/YourOwnSettings.xml clean install
or
mvn -s ~/.m2/YourOwnSettings.xml clean install

2. Jboss tasks:
 mvn jboss-as:deploy
 mvn jboss-as:redeploy
 mvn jboss-as:undeploy

3. Eclipse Maven clean:
(retired)
mvn eclipse:eclipse
mvn eclipse:clean
mvn install

4. set java version:
<project>
 [...]
 <build>
 [...]
 <plugins>
 <plugin>
 <groupId>org.apache.maven.plugins</groupId>
 <artifactId>maven-compiler-plugin</artifactId>
 <version>3.5.1</version>
 <configuration>
 <source>1.4</source>
 <target>1.4</target>
 </configuration>
 </plugin>
 </plugins>
 [...]
 </build>
 [...]
</project>

5. Missing Maven dependencies in Eclipse Project

   workaround to have an eclipse maven project

6. basic maven structure

src/main/java

 - src 
    - main 
          - java 
          - resources 
          - webapp 
     - test 
          - java 
          - resources 
          - target

7. packaging:

<packaging>jar</packaging>

8. executing from maven:

add the following plugin to pom.xml:
<plugin>
 <groupId>org.codehaus.mojo</groupId>
 <artifactId>exec-maven-plugin</artifactId>
 <version>1.2.1</version>
 <configuration>
 <mainClass>com.myorganisationname.common.App</mainClass>
 </configuration>
 </plugin>

and run it with:


mvn exec:java

9. skipping test:


<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-surefire-plugin</artifactId>
<version>2.19.1</version>
<configuration>
<skipTests>true</skipTests>
</configuration>
</plugin>
      or
 
 mvn install -DskipTests
 

 
10. Multiple Module Projects
<packaging>pom</packaging>


<modules>
<module>guide-ide-eclipse-site</module>
<module>guide-ide-eclipse-core</module>
<module>guide-ide-eclipse-module1</module>
</modules>


Add the parent to the POMs of the new modules:
 <parent>
 <groupId>guide.ide.eclipse</groupId>
 <artifactId>guide-ide-eclipse</artifactId>
 <version>1.0-SNAPSHOT</version>
 </parent>


mvn install
mvn eclipse:eclipse

http://maven.apache.org/plugins/maven-eclipse-plugin/reactor.html


11. web archetype

mvn archetype:generate -DgroupId=cl.devweb -DartifactId=wls_log_retrieval -DarchetypeArtifactId=maven-archetype-webapp -DinteractiveMode=false

12. copy dependencies:

 mvn dependency:copy-dependencies -DoutputDirectory=OUTPUT_DIR
 
13. tomcat

mvn tomcat7:deploy
mvn tomcat7:undeploy
mvn tomcat7:redeploy

14. verbose class

mvn test -DjvmArgs="-verbose:class"

15. web.xml-less
(servlet 3.0+)

<plugin>
 <groupId>org.apache.maven.plugins</groupId>
 <artifactId>maven-war-plugin</artifactId>
 <version>2.6</version>
 <configuration>
  <failOnMissingWebXml>false</failOnMissingWebXml>
 </configuration>
</plugin> 
 
 
16. weblogic
 
mvn com.oracle.weblogic:weblogic-maven-plugin:deploy

mvn com.oracle.weblogic:weblogic-maven-plugin:undeploy


            <plugin>
                <groupId>com.oracle.weblogic</groupId>
                <artifactId>weblogic-maven-plugin</artifactId>
                <version>12.1.3-0-0</version>
                <configuration>
                    <adminurl>t3://127.0.0.1:7001</adminurl>
                    <user>weblogic</user>
                    <password>welcome1</password>
                    <upload>true</upload>
                    <action>deploy</action>
                    <remote>true</remote>
                    <verbose>true</verbose>
                    <source>target/${project.artifactId}.${project.packaging}</source>
                    <name>${project.artifactId}</name>
                    <targets>AdminServer</targets>
                </configuration>
            </plugin>
 
17. debug flag

mvn -X
or

mvn -e


18. update (when it does not find jar)

mvn -U package

19. dependencies

mvn dependency:tree
     -Dverbose
 

My Blog List

Blog Archive

There was an error in this gadget

Disclaimer

The views expressed on this blog are my own and do not necessarily reflect the views of Oracle.