ROSE  0.9.9.139
Classes | Typedefs | Enumerations | Functions | Variables
Rose::BinaryAnalysis::Strings Namespace Reference

Description

Suport for finding strings in memory.

This namespace provides support for various kinds of strings in specimen memory, including an analysis that searches for strings in specimen memory. A string is a sequence of characters encoded in one of a variety of ways in memory. For instance, NUL-terminated ASCII is a common encoding from C compilers. The characters within the string must all satisfy some valid-character predicate. The terms used in this analysis are based on the Unicode standard, and are defined here in terms of string encoding (translation of a string as printed to a sequence of octets). Although this analysis can encode strings, its main purpose is decoding strings from an octet stream into a sequence of code points.

Unicode and its parallel standard, the ISO/IEC 10646 Universal Character Set, together constitute a modern, unified character encoding. Rather than mapping characters directly to octets (bytes), they separately define what characters are available, their numbering, how those numbers are encoded as a series of "code units" (limited-size numbers), and finally how those units are encoded as a stream of octets. The idea behind this decomposition is to establish a universal set of characters that can be encoded in a variety of ways. To describe this model correctly one needs more precise terms than "character set" and "character encoding." The terms used in the modern model follow:

A character repertoire is the full set of abstract characters that a system supports. The repertoire may be closed, i.e. no additions are allowed without creating a new standard (as is the case with ASCII and most of the ISO-8859 series), or it may be open, allowing additions (as is the case with Unicode and to a limited extent the Windows code pages). The characters in a given repertoire reflect decisions that have been made about how to divide writing systems into basic information units. The basic variants of the Latin, Greek and Cyrillic alphabets can be broken down into letters, digits, punctuation, and a few special characters such as the space, which can all be arranged in simple linear sequences that are displayed in the same order they are read. Even with these alphabets, however, diacritics pose a complication: they can be regarded either as part of a single character containing a letter and diacritic (known as a precomposed character), or as separate characters. The former allows a far simpler text handling system but the latter allows any letter/diacritic combination to be used in text. Ligatures pose similar problems. Other writing systems, such as Arabic and Hebrew, are represented with more complex character repertoires due to the need to accommodate things like bidirectional text and glyphs that are joined together in different ways for different situations.

A coded character set (CCS) specifies how to represent a repertoire of characters using a number of (typically non-negative) integer values called code points. For example, in a given repertoire, a character representing the capital letter "A" in the Latin alphabet might be assigned to the integer 65, the character for "B" to 66, and so on. A complete set of characters and corresponding integers is a coded character set. Multiple coded character sets may share the same repertoire; for example ISO/IEC 8859-1 and IBM code pages 037 and 500 all cover the same repertoire but map them to different codes. In a coded character set, each code point only represents one character, i.e., a coded character set is a function.

A character encoding form (CEF) specifies the conversion of a coded character set's integer codes into a set of limited-size integer code values that facilitate storage in a system that represents numbers in binary form using a fixed number of bits (i.e. practically any computer system). For example, a system that stores numeric information in 16-bit units would only be able to directly represent integers from 0 to 65,535 in each unit, but larger integers could be represented if more than one 16-bit unit could be used. This is what a CEF accommodates: it defines a way of mapping a single code point from a range of, say, 0 to 1.4 million, to a series of one or more code values from a range of, say, 0 to 65,535.

The simplest CEF system is simply to choose large enough units that the values from the coded character set can be encoded directly (one code point to one code value). This works well for coded character sets that fit in 8 bits (as most legacy non-CJK encodings do) and reasonably well for coded character sets that fit in 16 bits (such as early versions of Unicode). However, as the size of the coded character set increases (e.g. modern Unicode requires at least 21 bits/character), this becomes less and less efficient, and it is difficult to adapt existing systems to use larger code values. Therefore, most systems working with later versions of Unicode use either UTF-8, which maps Unicode code points to variable-length sequences of octets, or UTF-16, which maps Unicode code points to variable-length sequences of 16-bit words.

Next, a character encoding scheme (CES) specifies how the fixed-size integer code values should be mapped into an octet sequence suitable for saving on an octet-based file system or transmitting over an octet-based network. With Unicode, a simple character encoding scheme is used in most cases, simply specifying whether the bytes for each integer should be in big-endian or little-endian order (even this isn't needed with UTF-8). However, there are also compound character encoding schemes, which use escape sequences to switch between several simple schemes (such as ISO/IEC 2022), and compressing schemes, which try to minimise the number of bytes used per code unit (such as SCSU, BOCU, and Punycode).

Once the code points of a string are encoded as octets, the string as a whole needs some description to demarcate it from surrounding data. ROSE currently supports two styles of demarcation: length-encoded strings and terminated strings. A length-encoded string's code point octets are preceded by octets that encode the string length, usually in terms of the number of code points. Decoding such a string consists of decoding the length and then decoding code points until the required number of code points have been obtained. On the other hand, terminated strings are demarcated from surrounding data by a special code point such as the NUL character for ASCII strings. Decoding a terminated string consists of decoding code points until a terminator is found, then discarding the terminator.

Example 1

This example shows how to find all strings in memory that is readable but not writable using a list of common encodings such as C-style NUL-terminated printable ASCII, zero terminated UTF-16 little-endian, 2-byte little-endian length encoded ASCII, etc.

#include <rose/BinaryString.h> // binary analysis string support
MemoryMap map = ...; // initialized elsewhere
StringFinder finder; // holds settings
finder.settings().minLength = 5; // no strings shorter than 5 characters
finder.settings().maxLength = 65536; // ignore very long strings
finder.insertCommonEncoders(); // how to match strings
finder.find(map.require(MemoryMap::READABLE).prohibit(MemoryMap::WRITABLE));
BOOST_FOREACH (const EncodedString &string, finder.strings()) {
std::cout <<"string at " <<string.address() <<" for " <<string.size() <<" bytes\n";
std::cout <<"encoding: " <<string.encoder()->name() <<"\n";
std::cout <<"narrow value: \"" <<StringUtility::cEscape(string.narrow()) <<"\"\n"; // std::string
std::cout <<"wide value: " <<string.wide() <<"\n"; // std::wstring
}
// This works too if you're not picky about the output format
std::cout <<finder;

Example 2

The StringFinder analysis is tuned for searching for strings at unknown locations while trying to decode multiple encodings simultaneously. If all you want to do is read a single string from a known location having a known encoding then you're probabily better off reading it directly from the MemoryMap. The StringFinder analysis can be used for that, but it's probably overkill. In any case, here's the overkill version to find a 2-byte little endian length-encoded UTF-8 string:

#include <rose/BinaryString.h>
MemoryMap map = ...; // initialized elsewhere
rose_addr_t stringVa = ...; // starting address of string
StringFinder finder; // holds settings
finder.settings().minLength = 0; // no strings shorter than 5 characters
finder.settings().maxLength = 65536; // ignore very long strings
finder.encoder(lengthEncodedString(basicLengthEncoder(2, ByteOrder::ORDER_LSB), // 2-byte little-endian length
utf8CharacterEncodingForm(), // UTF-8 encoding
basicCharacterEncodingScheme(1), // 1:1 mapping to octets
anyCodePoint()); // allow any characters
std::wstring s;
BOOST_FOREACH (const EncodedString &string, finder.find(map.at(stringVa)).strings()) {
s = string.wide();
break;
}

Example 3

The encoders can also be used to decode directly from a stream of octets. For instance, lets say you have a vector of octets that map 1:1 to code values, and then you want to decode the code values as a UTF-8 stream to get some code points. All decoders are implemented as state machines to make it efficient to send the same octets to many decoders without having to rescan/reread from a memory map. The UTF-8 decoder decodes one octet at a time and when it enters the FINAL_STATE or COMPLETED_STATE then a decoded code value can be consumed.

#include <rose/BinaryString.h>
std::vector<Octet> octets = ...; // initialized elsewhere
// Instantiate the encoder/decoder. These things are all reference
// counted so there's no need to explicitly free them.
CodePoints codePoints;
BOOST_FOREACH (Octet octet, octets) {
CodeValue codeValue = octet; // 1:1 translation
if (isDone(utf8->decode(codeValue))) {
codePoints.push_back(utf8->consume());
} else if (utf8->state() == ERROR_STATE) {
utf8->reset(); // skip this code value
}
}

Classes

class  AnyCodePoint
 Matches any code point. More...
 
class  BasicCharacterEncodingScheme
 Basic character encoding scheme. More...
 
class  BasicLengthEncodingScheme
 Basic length encoding scheme. More...
 
class  CharacterEncodingForm
 Defines mapping between code points and code values. More...
 
class  CharacterEncodingScheme
 Defines the mapping between code values and octets. More...
 
class  CodePointPredicate
 Valid code point predicate. More...
 
class  EncodedString
 An encoder plus interval. More...
 
class  Exception
 Errors for string analysis. More...
 
class  LengthEncodedString
 Length-prefixed string encoding scheme. More...
 
class  LengthEncodingScheme
 Encoding for the length of a string. More...
 
class  NoopCharacterEncodingForm
 A no-op character encoding form. More...
 
class  PrintableAscii
 ASCII valid code points. More...
 
class  StringEncodingScheme
 String encoding scheme. More...
 
class  StringFinder
 Analysis to find encoded strings. More...
 
class  TerminatedString
 Terminated string encoding scheme. More...
 
class  Utf16CharacterEncodingForm
 UTF-16 character encoding form. More...
 
class  Utf8CharacterEncodingForm
 UTF-8 character encoding form. More...
 

Typedefs

typedef uint8_t Octet
 One byte in a sequence that encodes a code value. More...
 
typedef std::vector< OctetOctets
 A sequence of octets. More...
 
typedef unsigned CodeValue
 One value in a sequence that encodes a code point. More...
 
typedef std::vector< CodeValueCodeValues
 A sequence of code values. More...
 
typedef unsigned CodePoint
 One character in a coded character set. More...
 
typedef std::vector< CodePointCodePoints
 A sequence of code points, i.e., a string. More...
 

Enumerations

enum  State {
  FINAL_STATE = -1,
  COMPLETED_STATE = -2,
  INITIAL_STATE = -3,
  ERROR_STATE = -4,
  USER_DEFINED_0 = 0,
  USER_DEFINED_1 = 1,
  USER_DEFINED_2 = 2,
  USER_DEFINED_MAX = 128
}
 Decoder state. More...
 

Functions

bool isDone (State st)
 Returns true for COMPLETED_STATE or FINAL_STATE. More...
 
void initDiagnostics ()
 Initialize the diagnostics facility. More...
 
NoopCharacterEncodingForm::Ptr noopCharacterEncodingForm ()
 Returns a new no-op character encoding form. More...
 
Utf8CharacterEncodingForm::Ptr utf8CharacterEncodingForm ()
 Returns a new UTF-8 character encoding form. More...
 
Utf16CharacterEncodingForm::Ptr utf16CharacterEncodingForm ()
 Returns a new UTF-16 character encoding form. More...
 
BasicCharacterEncodingScheme::Ptr basicCharacterEncodingScheme (size_t octetsPerValue, ByteOrder::Endianness sex=ByteOrder::ORDER_UNSPECIFIED)
 Returns a new basic character encoding scheme. More...
 
BasicLengthEncodingScheme::Ptr basicLengthEncodingScheme (size_t octetsPerValue, ByteOrder::Endianness sex=ByteOrder::ORDER_UNSPECIFIED)
 Returns a new basic length encoding scheme. More...
 
PrintableAscii::Ptr printableAscii ()
 Returns a new printable ASCII predicate. More...
 
AnyCodePoint::Ptr anyCodePoint ()
 Returns a new predicate that matches all code points. More...
 
LengthEncodedString::Ptr lengthEncodedString (const LengthEncodingScheme::Ptr &les, const CharacterEncodingForm::Ptr &cef, const CharacterEncodingScheme::Ptr &ces, const CodePointPredicate::Ptr &cpp)
 Returns a new length-prefixed string encoder. More...
 
LengthEncodedString::Ptr lengthEncodedPrintableAscii (size_t lengthSize, ByteOrder::Endianness order=ByteOrder::ORDER_UNSPECIFIED)
 Returns a new encoder for length-encoded printable ASCII strings. More...
 
LengthEncodedString::Ptr lengthEncodedPrintableAsciiWide (size_t lengthSize, ByteOrder::Endianness order, size_t charSize)
 Returns a new encoder for multi-byte length-encoded printable ASCII strings. More...
 
TerminatedString::Ptr nulTerminatedPrintableAscii ()
 Returns a new encoder for NUL-terminated printable ASCII strings. More...
 
TerminatedString::Ptr nulTerminatedPrintableAsciiWide (size_t charSize, ByteOrder::Endianness order)
 Returns a new encoder for multi-byte NUL-terminated printable ASCII strings. More...
 
std::ostream & operator<< (std::ostream &, const StringFinder &)
 

Variables

Sawyer::Message::Facility mlog
 Diagnostics specific to string analysis. More...
 

Typedef Documentation

One byte in a sequence that encodes a code value.

Definition at line 168 of file BinaryString.h.

A sequence of octets.

Definition at line 169 of file BinaryString.h.

One value in a sequence that encodes a code point.

Definition at line 170 of file BinaryString.h.

A sequence of code values.

Definition at line 171 of file BinaryString.h.

One character in a coded character set.

Definition at line 172 of file BinaryString.h.

A sequence of code points, i.e., a string.

Definition at line 173 of file BinaryString.h.

Enumeration Type Documentation

Decoder state.

Negative values are reserved.

A decoder must follow these rules when transitioning from one state to another:

  • A decoder is in the INITIAL_STATE when it is constructed and after calling reset.
  • If the decoder is in an ERROR_STATE then decode does not change the state.
  • If the decoder is in the FINAL_STATE then decode transitions to ERROR_STATE.
  • If the decoder is in FINAL_STATE or COMPLETED state then consume transitions to INITIAL_STATE.

All other transitions are user defined.

Enumerator
FINAL_STATE 

Final state where nothing more can be decoded.

COMPLETED_STATE 

Completed state, but not a final state.

INITIAL_STATE 

Initial state just after a reset.

ERROR_STATE 

Decoder is in an error condition.

USER_DEFINED_0 

First user-defined value.

USER_DEFINED_1 

Second user-defined value.

USER_DEFINED_2 

Third user-defined value.

USER_DEFINED_MAX 

Maximum user-defined value.

Definition at line 194 of file BinaryString.h.

Function Documentation

bool Rose::BinaryAnalysis::Strings::isDone ( State  st)

Returns true for COMPLETED_STATE or FINAL_STATE.

void Rose::BinaryAnalysis::Strings::initDiagnostics ( )

Initialize the diagnostics facility.

This is called by Rose::Diagnostics::initialize.

NoopCharacterEncodingForm::Ptr Rose::BinaryAnalysis::Strings::noopCharacterEncodingForm ( )

Returns a new no-op character encoding form.

Utf8CharacterEncodingForm::Ptr Rose::BinaryAnalysis::Strings::utf8CharacterEncodingForm ( )

Returns a new UTF-8 character encoding form.

Utf16CharacterEncodingForm::Ptr Rose::BinaryAnalysis::Strings::utf16CharacterEncodingForm ( )

Returns a new UTF-16 character encoding form.

BasicCharacterEncodingScheme::Ptr Rose::BinaryAnalysis::Strings::basicCharacterEncodingScheme ( size_t  octetsPerValue,
ByteOrder::Endianness  sex = ByteOrder::ORDER_UNSPECIFIED 
)

Returns a new basic character encoding scheme.

BasicLengthEncodingScheme::Ptr Rose::BinaryAnalysis::Strings::basicLengthEncodingScheme ( size_t  octetsPerValue,
ByteOrder::Endianness  sex = ByteOrder::ORDER_UNSPECIFIED 
)

Returns a new basic length encoding scheme.

PrintableAscii::Ptr Rose::BinaryAnalysis::Strings::printableAscii ( )

Returns a new printable ASCII predicate.

AnyCodePoint::Ptr Rose::BinaryAnalysis::Strings::anyCodePoint ( )

Returns a new predicate that matches all code points.

LengthEncodedString::Ptr Rose::BinaryAnalysis::Strings::lengthEncodedString ( const LengthEncodingScheme::Ptr les,
const CharacterEncodingForm::Ptr cef,
const CharacterEncodingScheme::Ptr ces,
const CodePointPredicate::Ptr cpp 
)

Returns a new length-prefixed string encoder.

LengthEncodedString::Ptr Rose::BinaryAnalysis::Strings::lengthEncodedPrintableAscii ( size_t  lengthSize,
ByteOrder::Endianness  order = ByteOrder::ORDER_UNSPECIFIED 
)

Returns a new encoder for length-encoded printable ASCII strings.

A byte order must be specified for length encodings larger than a single byte.

LengthEncodedString::Ptr Rose::BinaryAnalysis::Strings::lengthEncodedPrintableAsciiWide ( size_t  lengthSize,
ByteOrder::Endianness  order,
size_t  charSize 
)

Returns a new encoder for multi-byte length-encoded printable ASCII strings.

TerminatedString::Ptr Rose::BinaryAnalysis::Strings::nulTerminatedPrintableAscii ( )

Returns a new encoder for NUL-terminated printable ASCII strings.

TerminatedString::Ptr Rose::BinaryAnalysis::Strings::nulTerminatedPrintableAsciiWide ( size_t  charSize,
ByteOrder::Endianness  order 
)

Returns a new encoder for multi-byte NUL-terminated printable ASCII strings.

Variable Documentation

Sawyer::Message::Facility Rose::BinaryAnalysis::Strings::mlog

Diagnostics specific to string analysis.