A utility for quickly searching presorted DNS names. Built around the Rapid7 rdns & fdns dataset.
How does it work?
This utility assumes the file provided is presorted (both alphabetical, and symbols).
The algorithm is pretty simple:
- Use a binary search algorithm to seek through the file, looking for a substring match against the query.
- Once a match is found, the file is scanned backwards in 10KB increments looking for a non-matching substring.
- Once a non-matching substring is found, the file is scanned forwards until all exact matches are returned.
There is a built-in limit system. This prevents 2 things:
- scanning too far backwards (
- scanning too far forwards after scanning backwards (
This allows for any input while stopping requests that are taking too long.
Additionally, this utility does not handle the edge cases(start/end) of files and will return an error if encountered.
go get the following packages:
# used for dnsgrep cli flags go get "github.com/jessevdk/go-flags" # used by the experimental server for http routing go get "github.com/gorilla/mux" # pull in a string reversal function go get "github.com/golang/example/stringutil"
The following steps were tested with Ubuntu 16.04 & go 1.11.5.
Generate fdns_a.sort.txt and rdns.sort.txt first using the scripts found in the scripts/ folder:
# Each of these scripts requires: # * 3 hours+ on an SSD # * 300GB+ temp disk space (under the same folder) # * ~65GB for output output (under the same folder) # * jq to be installed ./scripts/fdns_a.sh ./scripts/rdns.sh
Run the command line utility:
go run dnsgrep.go -f DNSBinarySearch/test_data.txt -i "amiccom.com.tw"
Run the experimental server in the same folder as fdns_a.sort & rdns.sort.txt:
go run experimentalServer.go
You can also run the command line utility using Docker:
docker build -t dnsgrep . docker run --rm -it -v "$PWD"/DNSBinarySearch:/files dnsgrep -f /files/test_data.txt -i ".amiccom.com.tw"
The source of this data referenced throughout this repository is Rapid7 Labs. Please review the Terms of Service: https://opendata.rapid7.com/about/
Stack Overflow References
- we need to sort with LC_COLLATE=C to also sort ., chars
- To sort a large file: split it into chunks, sort the chunks and then simply merge the results
See LICENSE file.