The regex-fsm
tool can be used to convert certain regular expressions to efficient matrix branching programs. These programs are suitable for use in obfuscation tools like the 5GenCrypto obfuscator.
cabal sandbox init
cabal install -j --depedencies-only
cabal build
To build with nix
nix-build
To develop regex-fsm
with nix
(highly recommended)
nix-shell -A regex-fsm.env
$ regex-fsm --regex '(0|1)*' --inputLength 10 --output output.json --verbose --chunks 1 --alphabet 01
Rep (Union (Lit '0') (Lit '1'))
ENFA
{ trans =
fromList
[ ( 1 , fromList [ ( Just '0' , fromList [ 2 ] ) ] )
, ( 2 , fromList [ ( Nothing , fromList [ 5 ] ) ] )
, ( 3 , fromList [ ( Just '1' , fromList [ 4 ] ) ] )
, ( 4 , fromList [ ( Nothing , fromList [ 5 ] ) ] )
, ( 5 , fromList [ ( Nothing , fromList [ 1 , 3 ] ) ] )
]
, start = 5
, final = fromList [ 5 ]
, states = fromList [ 1 , 2 , 3 , 4 , 5 ]
}
fromList
[ ( 1 , fromList [ 1 ] )
, ( 2 , fromList [ 1 , 2 , 3 , 5 ] )
, ( 3 , fromList [ 3 ] )
, ( 4 , fromList [ 1 , 3 , 4 , 5 ] )
, ( 5 , fromList [ 1 , 3 , 5 ] )
]
DFA
{ trans =
fromList
[ ( ( fromList [ 1 , 2 , 3 , 5 ] , '0' )
, fromList [ 1 , 2 , 3 , 5 ]
)
, ( ( fromList [ 1 , 2 , 3 , 5 ] , '1' )
, fromList [ 1 , 3 , 4 , 5 ]
)
, ( ( fromList [ 1 , 3 , 4 , 5 ] , '0' )
, fromList [ 1 , 2 , 3 , 5 ]
)
, ( ( fromList [ 1 , 3 , 4 , 5 ] , '1' )
, fromList [ 1 , 3 , 4 , 5 ]
)
, ( ( fromList [ 1 , 3 , 5 ] , '0' ) , fromList [ 1 , 2 , 3 , 5 ] )
, ( ( fromList [ 1 , 3 , 5 ] , '1' ) , fromList [ 1 , 3 , 4 , 5 ] )
]
, start = fromList [ 1 , 3 , 5 ]
, finals =
fromList
[ fromList [ 1 , 2 , 3 , 5 ]
, fromList [ 1 , 3 , 4 , 5 ]
, fromList [ 1 , 3 , 5 ]
]
}
DFA
{ trans =
fromList
[ ( ( fromList [ 1 , 3 , 5 ] , '0' ) , fromList [ 1 , 3 , 5 ] )
, ( ( fromList [ 1 , 3 , 5 ] , '1' ) , fromList [ 1 , 3 , 5 ] )
]
, start = fromList [ 1 , 3 , 5 ]
, finals = fromList [ fromList [ 1 , 3 , 5 ] ]
}
[ fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 1 ) , ( "1" , 1 ) ]
, fromList [ ( "0" , 0 ) , ( "1" , 0 ) ]
]
Suitable for use with the 5Gen obfuscation tool
{
"steps": [{"0":[[1]],"1":[[1]],"position":"0"},
{"0":[[1]],"1":[[1]],"position":"1"},
{"0":[[1]],"1":[[1]],"position":"2"},
{"0":[[1]],"1":[[1]],"position":"3"},
{"0":[[1]],"1":[[1]],"position":"4"},
{"0":[[1]],"1":[[1]],"position":"5"},
{"0":[[1]],"1":[[1]],"position":"6"},
{"0":[[1]],"1":[[1]],"position":"7"},
{"0":[[1]],"1":[[1]],"position":"8"},
{"0":[[0]],"1":[[0]],"position":"9"}]
,"outputs": [["false","true"]]
}
A further optimization before matrix encoding is premultiplication. This will decrease multilinearity, but can increase time spent encoding if the matrix count increases overall. To premultiply matrices, specify a chunk size that is a multiple of the input size.
$ regex-fsm --regex '(0|1)*' --inputLength 10 --output output.json --verbose --chunks 2 --alphabet 01
[ fromList [ ( "00" , 1 ) , ( "01" , 1 ) , ( "10" , 1 ) , ( "11" , 1 ) ]
, fromList [ ( "00" , 1 ) , ( "01" , 1 ) , ( "10" , 1 ) , ( "11" , 1 ) ]
, fromList [ ( "00" , 1 ) , ( "01" , 1 ) , ( "10" , 1 ) , ( "11" , 1 ) ]
, fromList [ ( "00" , 1 ) , ( "01" , 1 ) , ( "10" , 1 ) , ( "11" , 1 ) ]
, fromList [ ( "00" , 0 ) , ( "01" , 0 ) , ( "10" , 0 ) , ( "11" , 0 ) ]
]
To execute criterion benchmarks of various compiler phases.
$ nix-build
$ ./result/bin/benchmarks -o index.html
$ open index.html
To run the entire pipeline once against the 5Gen obfuscator tool, execute obfuscator-tests
with a security parameter (defaults to 40
).
$ nix-build
$ ./result/bin/obfuscator-tests --secParam 8
To run the entire test suite (takes a long time and is very resource intensive).
$ nix-build
$ ./result/bin/obfuscator-tests --runTestSuites
To run unit tests, simply nix-build
, unit tests are run automatically.
$ nix-build
...
Linking dist/build/tests/tests ...
running tests
Running 1 test suites...
Test suite tests: RUNNING...
Test suite tests: PASS
Test suite logged to: dist/test/regex-fsm-0.1.0.0-tests.log
1 of 1 test suites (1 of 1 test cases) passed.
BSD3 (c) Galois Inc.