Forensic-Tool Development with Rust

Like in other established forensic disciplines the forensic soundness or reliability of digital evidence is determined by the validity and correctness of forensic software used in examination. In other words, to guarantee that the digital evidence is forensically sound, all tools used to collect, preserve and analyse digital evidences must be validated. Tool validation can also be formally required to comply with standards like the ISO 17025 Laboratory Accreditation standard.

It should be noted that the forensic community’s definition of validation and verification differs from what is used in software engineering. Two commonly used definitions state the following:

A short and catchy definition was proposed by Beckett and Slay [5]:

It means that establishing a reliable technical method to observe a cause and effect relation between a human action and a resulting artefact is called validation. The test, whether a technical device is suitable or not to execute the above method reliably, is called verification.

Craiger [6 p. 92] defines validation and verification as follows:

Common to both definitions of validation is the mapping of the tool’s requirements to tests confirming that they fully and correctly implemented. At first glance the above approach might seem simple to implement but in many cases it is impossible to carry out:

To cope with this difficulty Beckett and Slay [5] suggest a model so called Model of tool neutral testing or functionality oriented validation. Instead of testing if a software product meets all its requirements an independent set of forensic functions and their specifications is defined. This allows to decouple the validation procedure from the implementation of the forensic tool itself. A forensic function is an activity required in forensic investigation that produces known valid results for a given set of test cases.

The first difficulty consists in breaking down the multitude of activities in forensic investigation in function categories and subcategories as shown in Figure 2, “An overview of searching function” [3 p. 17].

The search target mapping as shown below illustrates under the subcategory “Character encoding” the main deficit of GNU-strings supporting only ASCII encoding. In global cyberspace forensic tools must identify a multitude of encodings. This leads us to the main motivation and requirement of Strings­ext: Section 4.2, “Character encoding support”

The functionality oriented validation can be classified as “black box testing” examining functionality without any knowledge of internal implementation, without seeing the source code. “Black box testing” of functions and their specifications allows conducting numerous tests with acceptable costs. It requires test cases with known valid results. With Strings­ext this approach is used to test the correctness of the implementation when dealing with large real-world data (cf. Section 4.8, “Functionality oriented validation”).

When the internal computation is as complex as in Strings­ext, “white box testing” is essential. The method chosen in the present development “test harness” is detailed in the Section 4.7, “Automated test framework”.

The relation between the criminal and the forensic examiner can be described as follows: “Make it hard for them to find you and impossible for them to prove they found you” [7]. Have your recognised the statement? Is widely cited when it comes to define anti-forensics. This traditional "hide and seek" relation might soon take a new dimension: Eggendorfer [8] stresses with good reasons that forensic tools are software too and therefor vulnerable to attacks.

GNU-strings is part of the GNU binutils collection which became publicly available in 1999 [9]. Today it has reached the notable age of 17 years. GNU-strings is a comparatively small program with 724 lines of code only. It is all the more surprising that in 2014 the security researcher Zalewski discovered a serious security vulnerability CVE-2014-8485 [10].

Zalewski headlined his bug report “Don’t run strings on untrusted files.” Needless to say that this advice can not be followed in the context of a forensic investigation. In the meantime the bug was fixed but users remain confused and bewildered.

The above bug is part of a vulnerability class related to memory safety problems. GNU strings is written in C, a language whose abstractions can not guarantee memory safety. In order to exclude potential vulnerabilities of the same kind from the start, Strings­ext was developed with the Rust programming language which is discussed further in the Chapter 5, The Rust programming language.

The searching domain in forensic investigations is often as large as the seized data-carrier. Nowadays hard-disk images hold several TiB of data. Memory images of the RAM are smaller, but still some GiB in size. In order to address so big search domains, forensic software must operate very efficiently. This is why forensic software is often programmed in C or C++. But not only the programming language matters: Efficient code requires carefully chosen abstractions, efficient algorithms avoiding un­ne­ces­sary data-copies and program-loops.

As discussed above the main motivation for developing Strings­ext are the missing multi-byte character encoding semantics in GNU-strings. GNU-strings encoding support consists of a rudimentary filter accessed with the option --encoding. For details see the Table 1, “GNU-strings manual page (extract)”. How well does GNU-strings detect Unicode?

The Figure 4, “Test case international character encodings” shows the content of a text file chosen as test case.

The above file is then is converted into different encodings using the following script:

In order to observe GNU-strings Unicode detection capabilities, all the above test-files are searched for valid graphic strings with the command strings using all possible variation of its encoding filter.

The following figures show GNU-strings output.

As shown in the Figure 6, “GNU-strings, single-8-bit option”, the encoding filter -e S is the only filter that finds international characters at all.

The Figure 7, “GNU-strings, 16-bit little-endian option” and the Figure 8, “GNU-strings, 16-bit big-endian option” confirm that with UTF-16 no international characters are recognized. The same holds true for UTF-32: see Figure 9, “GNU-strings, 32-bit little-endian option” and Figure 10, “GNU-strings, 32-bit big-endian option”. This limitation is of particular importance in forensic investigations: The Microsoft-Windows operating system handles Unicode characters in memory as 2 byte UTF-16 words. As a result when dealing with Microsoft-Windows memory images, GNU-strings is not able to detect any international characters!

It should not be forgotten that GNU-strings can not analyse multi-byte encodings in general. This is why other very common encodings e.g. big5 or koi8-r were not tested even though they are widely used.

The above-outlined limitations led to Strings­ext's main requirement: Section 4.2, “Character encoding support”.

The following script ^[1] shows how forensic examiners typically use the program GNU-strings`:

Please refer to Table 1, “GNU-strings manual page (extract)” for details about the used options above.

The first and only parameter of the above script $1 is the filename of the binary data to be examined.

With the above observations of how GNU-strings is used, I define the following requirements for the new development Strings­ext in order to improve its usefulness and/or usability:

The user interface of Strings­ext should reproduce GNU-strings' user interface as close as possible. Where applicable, options should follow the same syntax. When used in ASCII-only mode, the output of Strings­ext should be bit-identical with GNU-strings' output.

Besides ASCII, Strings­ext should support common multi-byte encodings like UTF-8, UTF-16 big Endian, UTF-16 little Endian, KOI8-R, KOI8U, BIG5, EUC-JP and others. The string findings in these encodings should be presented in chronological order and merged. The user should be able to spe­cify more than one encoding at the same time.

Each search encoding specified by the user is assigned to a separate thread hereafter referred as “scanner”.

Because of the differing complexity of the decoding process depending on the chosen encoding, the scanners run at different speeds. In order to li­mit memory consumption it must be assured that the scanners do not drift apart. This is guaranteed by operating in batch mode: all scanners operate sim­ul­tan­eously on the same search field chunk. Only when all scanners have finished searching and reported their findings, the next chunk can be processed.

When a scanner completes the current search field chunk, it sends its findings to the merger-thread. When all threads' findings are collected, the merging algorithm brings them in chronological order. Then the printer formats the findings and prints them to the output channel.

Strings­ext should have at least one print mode allowing post-treatment with line-oriented tools like grep, agrep or a spreadsheet program. The output of the other modes should be optimised for human readability.

To take into account the increased requirements of the forensic community in correctness and reliability the test driven development method should be applied. Unit tests programming various test cases check automatically for correct results. Furthermore, the chosen methodology makes sure that the unit-tests are working as intended. For details please refer to Chapter 6, Software development process and testing.

Well designed unit testing reduces the defect rate significantly. Unit testing allows to verify whether a piece of code produces valid output for a given test case. The difficulty consists in finding relevant test cases challenging all internal states of the program. Unfortunately no indicators arise from these tests on how the program behaves on input data other then the test cases. This is why tests under real world conditions are indispensable.

In addition to the mentioned unit tests Strings­ext should be evaluated according the functionality oriented validation method. This common method to validate forensic software is discussed in detail in the Section 2.1, “Tool validation”. In the present case a comparative test should be executed as follows:

This requirement emerges from special requirements on tools in forensic investigations which are detailed in the Section 2.3, “Code efficiency”.

Applied to Strings­ext the following is required:

The programming language should

Programming style and techniques should promote efficient coding by

In the narrow sense, “security coding” is more a design goal than a functional requirement. Secure coding denotes the practice of developing computer software in a way that reduces the accidental introduction of security vulnerabilities to a level that can be fully mitigated in operational environments. This reduction is accomplished by preventing coding errors or discovering and eliminating security flaws during implementation and testing.

From the code security point of view the requirement defined in the Section 4.2, “Character encoding support” is the most critical: The NIST National Vulnerability Database lists under the heading “character encoding” 22 vulnerabilities. To give an idea of the severity of this kind of vul­ne­ra­bi­li­ty, here a short summary of the most recent one, published in September 2016, is CVE-2016-3861:

The technical cause of the CVE-2016-3861 vulnerability is an exploitable heap-based buffer overflow. Buffer overflows belong to the vulnerability category memory safety issues which are typical for the system programming languages C and C++.

To avoid similar vulnerabilities, Strings­ext is implemented using the Rust programming framework. A short description of the programming language and its security guaranties can be found in the Chapter 5, The Rust programming language.

All memory-related problems in C and C++ come from the fact that C programs can unrestrainedly manipulate pointer to variables and objects outside of their memory location and their lifetime. The Table 5, “Common weaknesses in C/C++ that affect memory” shows a selection of most common memory safety related vulnerabilities [12]. This is why memory safe languages like Java do not give programmers direct and uncontrolled access to pointers. The Java compiler achieves this with a resource costly runtime and a garbage collector. The related additional costs in terms of runtime resources exclude programming language like Java for most forensic tool development.

For many years program efficiency and memory safety seemed to be an insurmountable discrepancy. Now, after 10 years of development, a new programming language called Rust promises to cope with this balancing act. Rust's main innovation is the introduction of semantics defining data ownership. This new programming paradigm allows the compiler to guarantee memory safety at compile-time. Thus, no resource costly runtime is needed for that purpose. In Rust most of the weaknesses listed in Table 5, “Common weaknesses in C/C++ that affect memory” are already detected at compile time. Moreover, Rust's memory safety guarantees that none of these weaknesses can result in an undefined system state or provoke data leakage.

Rust's main innovation is the introduction of new semantics defining ownership and borrowing. They translate to the following set of rules which Rust’s type system enforces at compile time:

By observing the above rules Rust regulates how resources are shared within different scopes. Memory problems can only occur when a resource is referenced by multiple pointers (aliasing) and when it is mutable at the same time. In contrast to other languages, Rust's semantics allow the type system to ensure at compile time that simultaneous aliasing and mutation mutually exclude each other. As the check is performed at compile-time, no run-time code is necessary. Furthermore, Rust does not need a garbage collector: when owned data goes out of scope it is immediately destroyed.

The following code samples [13] illustrate how well the Rust compiler detects non-obvious hidden memory safety issues.

The following sample code returns a pointer to a stack allocated resource s that is freed at the end of the function: we find ourselves with a “Use after free” condition! The compiler aborts with the error message s does not live long enough.

Here the corrected memory safe code:

The push() method in the next example causes the backing storage of data to be reallocated. As a result we have a dangling pointer, here x, vulnerability! The code does not compile in Rust.

Here the corrected memory safe version that compiles:

A very common group of programming mistakes is related to improper handling of indexes especially in loops, e.g. “CWE-129: Improper Validation of Array Index” (cf. Table 7, “Common weaknesses in C/C++ affecting memory avoidable with iterators”[12]).

In addition to traditional imperative loop control structures, Rust offers efficient iteration with functional style iterators. Like in Haskell iterators are lazy and avoid allocating memory for intermediate structures (you allocate just when you call .collect()).

Besides performance considerations, iterators considerably enhance the robustness and safety of programs. They enable the programmer to iterate through vectors without indexes! The following code shows an example.

It must be noted that even with iterators out of bounds-errors may occur. Nevertheless, iterators should be preferred because they reduce the probability of errors related to indexes drastically.

It is the language design goal Zero-Cost Abstractions that makes the C/C++ language so efficient and suitable for system programming. It means that libraries implementing abstractions, e.g. vectors and strings, must be designed in a way that the compiled binary is as efficient as if the program had been written in Assembly. This is best illustrated with memory layouts: Memory layout of a Rust vector shows a vector in Rust. Its memory layout is very similar is to a vector in C/C++.

In contrast, the memory safe language Java enforces a uniform internal representation of data. In Java a vector has 2 indirections instead of 1 compared to Rust and C/C++ (cf. Memory layout of a Java vector). As the data could be represented in a more efficient way in memory, we see that Java does not prioritise the Zero-Cost-Abstraction goal.

This chapter introduces two fields of Rust programming that I struggled with at the beginning. Even when the code does not explicitly annotate lifetimes and does not use dynamic dispatching, the underlying concepts are vital for the understanding of Rust’s error messages.

Based on the functional requirements described in the Chapter 4, Specifications and especially in the Section 4.3, “Concurrent scanning”, the Section 4.4, “Batch processing” and the Section 4.5, “Merge findings” the algorithm of the data-flow was defined (cf. Section 7.3, “Scanner Algorithm”).

Once a todo-list was established, Strings­ext’s core functions were identified and ordered by risk: What would be the impact on the whole project if the implementation of a certain function turns out to be impossible or difficult to realise in the Rust?

Specifically, sorted after risk:

For every core function alternative technical solutions were suggested, implemented, tested and evaluated (cf. Chapter 7, Analysis and Design). This approach allowed at an early assurance that Rust provides abstractions and solutions for each of the core functions. It needs to be emphasized that the above isolated partial solutions do not reveal any indications about their intercompatibility or temporal behaviour. This risk is addressed in the next step.

Regarding the above core functions the encoder library presented the highest risk. Was its low level interface suitable for the intended purpose? Was it fast enough? In order to answer these questions a first prototype with very little functionality was built. The first prototype showed as proof of concept, that the library meets the expectations.

From this point on, the actual development of Strings­ext was launched. To meet the high demands in reliability and correctness it had been developed using the Test Driven Development (TDD) method suggested by Beck [15].

Documentation is an important part of any software project. Rust projects and APIs are documented by annotating the source code with special comment-tags \\\ and \\!. Annotations are usually placed just before the line it refers to. Documentation comments are written in Markdown. The Rust distribution includes a tool, Rustdoc, that generates the documentation. Rustdoc's consists of linked html pages, similar to Javadoc. The Strings­ext project makes extensive use of Rust's documentation feature.

The user manual is written in reStructuredText format and compiled to a man-page with Docutils (cf. Table 10, “Manual page - stringsext - version 1.0”).

The Data processing and threads shows the data flow in Strings­ext. All scanner instances as well as the merger-printer are designed as threads. Rust uses OS-level threads and its type and ownership model guarantees the absence of data races, which are defined as:

Rust supports by default two models of inter-thread communication:

stringsext imports the crate “scoped_threadpool” used to distribute the shared-memory input_slice to its scanner-threads. Once a scanner has accomplished its mission, it sends its result through a dedicated message channel to the merger-printer-thread. The following code extract illustrates the implementation:

Concurrent computing gives no guarantee in which order partial-output is available. With regard to Strings­ext this means that the order in which the different scanners report their results, depend on racing conditions that are not predictable. In order to illustrate this phenomenon, the Figure 11, “Non reproducible output” shows the merged output of Strings­ext. It is not surprising that for example at position 47 and c47 the scanners ASCII and UTF-8 find strings at the same location since the ASCII-encoding is a subset of the UTF-8 encoding. Whilst at position 47 the output of the UTF-8 scanner is first listed, at position c47 the output of the ASCII-scanner is printed first! Even though the output of Strings­ext is always correct, the order in which the results are presented changes unpredictably!

The retained solution is to extend the sort by criteria which is used by the merger thread to order the findings. Now it proceeds as follows: first it sorts by the offset of the finding and then by the encoder name that has reported the finding. The Figure 12, “Reproducible output” shows the result. Please note that for all identical positions the ASCII-scanner result is always listed first.

The input data is processed in batches chunk by chunk. Each chunk is browsed in parallel by several “scanner” threads. This section describes the algorithm:

The above algorithm splits the search field into overlapping memory chunks called WIN_LEN. Every chunk is also split into 3 fields: WIN_STEP, FINISH_STR_BUF and UTF8_LEN_MAX. This section explains how the algorithm operates on these fields.

WIN_LEN is the length of the memory chunk in which strings are searched in parallel.

As shown above, WIN_LEN defines an overlapping window that advances WIN_STEP bytes each iteration.

WIN_LEN = WIN_STEP + WIN_OVERLAP is the size of the memory chunk that is processed during one iteration. A string is only found when it starts within the WIN_STEP interval. The remaining bytes can reach into WIN_OVERLAP or even beyond WIN_LEN. In the latter case the string is split.

WIN_OVERLAP is the overlapping fragment of the window. The overlapping fragment is used to read some bytes ahead when the string is not finished. WIN_OVERLAP is subject to certain conditions: For example the overlapping part must be smaller than WIN_STEP. Furthermore, the size of FINISH_STR_BUF = WIN_OVERLAP - UTF8_LEN_MAX determines the number of bytes at the beginning of a string that are guaranteed not to be spit.

This size matters because the scanner counts the length of its findings. If a string is too short (< ARG.flag_bytes), it will be skipped. To avoid that a string with the required size gets too short because of splitting, we claim the following condition:

In practice we chose for FINISH_STR_BUF a bigger size than the minimum to avoid splitting of strings as much as possible. Please refer to the test function test_constants() for more details about constraints on constants. The test checks all the necessary conditions on constants to guarantee the correct functioning of the program.

The scanner tries to read strings in WIN_LEN as far as it can. The first invalid byte indicates the end of a string and the scanner holds for a moment to store its finding. Then it starts searching further until the next string is found. Once WIN_OVERLAP is entered the search ends and the start variable is updated so that it now points to restart-at-invalid as shown in the next figure. This way the next iteration can continue at the same place the previous had stopped.

The next iteration can identify this situation because the start pointer points into the previous FINISH_STR_BUF interval.

A special treatment is required when a sting extends slightly beyond WIN_LEN. In this case the scanner most likely runs into an incomplete multi-byte character just before the end of WIN_LEN. The cut surface restart-at-cut is then somewhere in the UTF8_LEN_MAX interval as the following figure shows.

The remaining part will be printed later during the next iteration. But how does the following iteration know if a string had been cut by the previous iteration? In the next interval the scanner first checks if the previous scan ended in the UTF8_LEN_MAX interval. If yes, we know the string has been cut and we the remaining bytes at the beginning of the new interval regardless of their size.

To satisfy all the above constraints WIN_OVERLAP must satisfy two conditions concurrently:

As Files are accessed through 4KiB memory pages, we choose WIN_STEP to be a multiple of 4096 bytes.

The from_stdin() function implements its own reader buffer BUF_LEN to allow stepping with overlapping windows. The algorithm requires that BUF_LEN is greater or equal than WIN_LEN (the greater the better the performance).

Every time BUF_LEN is full, the last WIN_OVERLAP part must be copied from the end to the beginning of BUF_LEN. As copying is an expensive operation we choose:

The above reduces the copying to every 4th iteration.

In Unicode the maximum number of bytes a multi-byte-character can occupy in memory is 6 bytes.

To meet the requirements defined in the Section 4.2, “Character encoding support” Strings­ext's scanners perform a code conversion of their findings towards UTF-8 (see also Data processing and threads). Encoding conversion is a very complex matter: the Unicode specification alone has 1036 pages [18]! And Unicode is not the only encoding involved in Strings­ext's data processing.

It will come as no surprise that encoding conversion is related to numerous vulnerabilities (see the Section 4.10, “Secure coding” for details).

Basically, there are two ways to interface a third party library in Rust:

In order to address potential security issues discussed in the Section 4.10, “Secure coding” the second option “native Rust library” had been chosen. Strings­ext uses the so called rust/encoding library developed by Seonghoon [19].

rust/encoding provides encoder and decoder functionality for the following encodings specified by the WHATWG encoding standard:

The rust/encoding library was originally not designed to search for strings in binary data. Nevertheless, the low level API function decoder.raw_feed() returns and decodes chunks of valid strings found in the input stream. Those valid strings are then always re-encoded to UTF-8 and comprise:

As the rust/encoding library returns valid strings and Strings­ext prints by default only graphical strings, and additional filter must be applied:

All scanners use the above filter unless the command-line option --control-chars=p is given. Then the whole valid string is printed with all its control characters.

The only exception to this occurs for the options -e ascii -c i. This combination invokes a specially designed ASCII-graphical-strings-only decoder. This approach made it possible to generate a bit identical output compared to GNU-strings for this setting.

The option --control-chars=r addresses especially the requirement defined in the Section 4.6, “Facilitate post-treatment”. All control characters are replaced by \u{fffd} keeping the filtered string always in one line. Together with the formatting option -t the printed lines have the following syntax:

GNU-strings can read its input from a file, or from a pipe. Both requires different optimisation strategies. The fastest way to read a file sequentially is through the memory mapping kernel interface. danburkert/memmap-rs is a Rust library for cross-platform memory-mapped file IO. An interesting feature of memory mapping is that it can map files much larger than the available RAM to a virtual address space. This allows to map the whole file regards to its size and iterate over it with a sliding window. The following code extract shows this technique. Note that there is only one call of the Mmap::open() wrapper occurring outside the loop. This reduces the overhead caused by the wrapper.

An alternative technique consists mapping memory pages sequentially page by page. The following code shows this approach. Note that the call of Mmap::open_with_offset() happens inside the loop!

Tests with big files showed that memory mapping page by page is faster despite its overhead. One reason is that the other solution does not launch the scanner right from the start: the operating system reads the whole data in memory before giving the control back to the calling program. This does not only consume a lot of memory but also holds back the scanners when the program starts. This is why the solution Memory mapping page by page was selected: it reads only very few memory pages into memory and the scanner can start their work much earlier.

Note that the function as_slice() is tagged “unsafe”. It means that the file-reading operation is only safe as long as no other process writes that file simultaneously. I consider this requirement to be met for all use cases of Strings­ext and we do not implement any additional file locking mechanism.

The second operation mode “reading input from a pipe” raised another challenge: None of the standard input readers is able to read by overlapping chunks. To solve the problem a circular-buffer was implemented. The following shows an extract of the source code.

The merger-printer thread in the Data processing and threads receives vectors of Findings from the connected upstream scanners. Every input vector is sorted by memory offset.

To merge the input vectors two alternative solutions have been developed.

The first solution is based on a contribution of Jake Goulding, aka Shepmaster, who posted the following code realising an iterator able to merge 2 vectors [20].

The following testing code illustrates how to merge two vectors.

Jake Goulding’s code, as shown above, can only merge two vectors. The following macro, realised by the author of this present work, extends the above code by adding successively iterators. The resulting algorithm to find the next element is basically a linear search. Its complexity is O(N * k), where N is the total length of iterables and k is the number of iterables.

The following testing code illustrates how to merge 5 vectors.

For test purposes, the above 4 code samples can be concatenated in one file.

The benefit of this solution is its simplicity and that it does not require any external library. Sure, linear search is not the fastest algorithm, but seeing the little number of vectors we have to merge this is not necessarily a drawback.

Shortly after I implemented the above solution, the iterator kmerge was published in the rust/itertools library. It implements the heapsort algorithm. The complexity of the approach is O(N * log(k)), where N is the total length of iterables and k is the number of iterables. Its better performance, compared to the first solution, is practically negligible in the present case as number of iterables is relatively small.

The next testing code sample shows how to merge 3 vectors.

For Strings­ext I finally chose the second solution with kmerge. Its slightly better performance is surely desirable, but most of all it was my intention of keeping Strings­ext's code base as small as possible that led to the decision using the external kmerge-function of the rust/itertools library.

To evaluate Strings­ext's capabilities to handle international scripts with Unicode we chose the same text file as input we used with GNU-strings in the Section 3.1, “Test case 1 - International character encodings”:

The following bash-script automates the test case generation: To provide a copy of the test file in UTF-8, UTF-16be, UTF-16le, UTF-32be and UTF-32le encodings the Unix tool iconv is used.

The second part of the script feeds the generated copies one by one into Strings­ext. The options -e ascii -e utf-8 -e utf-16be -e utf-16le instruct Strings­ext to search for the following encodings: ASCII, UTF-8, UTF-16be, UTF-16le. Please refer to Table 10, “Manual page - stringsext - version 1.0” for details on stingsext's command-line options.

The following figures show stringsext's output, case by case.

The following table shows the man-page user documentation. It is typeset as reStructuredText and compiled using the Sphinx tool [21].

Rust’s build in benchmarking feature allows to clock the time of unit testing code. At the time of this writing this feature is only available with the “nightly” distribution of the Rust compiler. It is especially valuable when used together with the test driven development method (cf. Section 6.3, “Test Driven Development”): First the programmer implements the unit testing code for a new feature. The second step consists in finding alternative solutions to implement this new feature. Using Rust’s benchmarking the programmer can take performance consideration into account at very early state when he is still exploring alternative solutions for the to be tested unit.

A second approach to benchmark software is to monitor the system resource usage of the running binary. The Linux-tool time runs programs and summarize system resource usage. This way we can compare the performance of GNU-strings and Stringsext. For this purpose the following script runs a series of 6 benchmark tests. In benchmark test 2 Stringsext is launched with only one ASCII scanner producing the same output as GNU-strings in benchmark test 1.

The benchmark tests 3 to 5 are designed to study how Strings­ext scale with more than one ASCII-scanner. The last benchmark 6 is a more realistic test case with 4 different scanners: ASCII, UTF-8, UTF-16BE and UTF-16LE.

All test operate on the same input data: a partition image with a Linux kernel dev-sda.raw.

The script is executed on a laptop with an Intel Core i5-2540M, 2.60GHz CPU.

When launched as pure ASCII scanner Stringsext produces the same output as GNU-strings, but 2.4 times slower. This result is very satisfactory: Strings­ext's ASCII-only mode is only one special usage scenario among many others requiring complex time costly computing. When scanning for other encodings or for more than one encoding in parallel Strings­ext can play off its particular strengths. It is best run on modern hardware with four or more kernels.

In the Section 8.3, “Benchmarking and field experiment” we could convince ourselves that Strings­ext produces accurate results timely. But how do matters stand with the other requirements defined in the Chapter 4, Specifications? Specifically:

Strings­ext meets all requirements defined in the Chapter 4, Specifications. Because of the inherent properties of the UTF-16 encoding, the UTF-16 scanners produce many false positives when run over binary data. A possible solution is suggested at the end of the Section 8.1.2, “UTF-16 encoded input”.

Before publishing Strings­ext, a beta-version had been tested by a small group of forensic practitioners. In addition, the participants were invited to report back about desirable extensions or missing features:

Regarding additional encodings: Strings­ext is designed to be extensible. Adding further encodings other than the ones listed in the Section 7.5, “Integration with a decoder library” is beyond the scope of this project, but it is made easy: As working sample encoding extension ASCII_GRAPHIC can be found in the source code of Strings­ext in src/codec/ascii.rs. The request “ordered list” was implemented in version 0.9.5.

So far Strings­ext’s search algorithm is based solely on finding valid byte sequences for a given encoding. Strings­ext is a pure data processing system in the sense that there are no semantics weather the resulting graphical character sequences make any “sense”. The following suggestion received by email [22] goes far beyond this limitation.

This above idea opens the very interesting research field of Computational Linguistics. Language detection in character sequences requires a linguistic model of “what is a word” in a given human language. Thus, with the suggested enhancement Strings­ext would become a language processing system.

Jurafsky [23 p. 3] illustrates the conceptual difference between a data processing system and a language processing system as follows: “What distinguishes language processing applications from other data processing systems is their use of knowledge of language. Consider the Unix wc program, which counts the total number of bytes, words, and lines in a text fi le. When used to count bytes and lines, wc is an ordinary data processing application. However, when it is used to count the words in a file, it requires knowledge about what it means to be a word and thus becomes a language processing system.” Applied to Strings­ext “the knowledge about what it means to be a word” comprises a probabilistic model about the likelihood that a certain character sequence represent a word in a given human language. It is clear that the approach is beyond the scope of this project. Nevertheless, the exiting challenge could be tackled in future research projects.

Strings­ext is licensed under the Apache Licence, Version 2.0; you may not use this program except in compliance with the Licence. You may obtain a copy of the Licence at http://www.apache.org/licenses/LICENSE-2.0. The copyright remains with the author Jens Getreu.

Unless required by applicable law or agreed to in writing, software dis­tri­bu­ted under the Licence is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the Licence for the specific language governing permissions and limitations under the Licence.

The source code including its inline source documentation is hosted on Github [1]: https://github.com/getreu/stringsext. The project’s main page has links to the developer documentation and to the compiled binaries for various architectures.