# Function ID

## Function ID

### Overview

Function ID is an analyzer that performs function identification analysis on a program. For each function, the analyzer computes a hash of its body and uses this as a key to look up matching functions in an indexed database of known software. The recovered function name, and other meta-data about the library it is contained in, is applied to the program.

Function ID is suitable for identifying statically linked libraries or other software where the compiled form of the functions does not change. Because of the hashing strategy, functions remain identifiable even if the library is relocated during linking. Larger changes to the compilation process of the library however will likely prevent successful searches. Function ID databases are necessarily targeted to a specific processor.

Function ID generally runs as part of Auto Analysis but can also be initiated at any time by the user from the One Shot menu. Ghidra also comes with a , which provides more control over which databases to apply, and allows users to create and populate their own databases.

By default, Ghidra ships with databases that search for statically linked libraries from Microsoft Visual Studio for the x86 processor. These have been broken apart into separate Function ID databases, based on 32-bit or 64-code and the version of Visual Studio. Within each database, there are a two library variants -- one for debug versions and one for production.

#### Hashing

Function ID works by calculating a cumulative hash over all the machine instructions that make up the body of a function. For each function, two different 64-bit hashes are computed: a full hash and a specific hash. Both schemes hash the individual instructions of the function body in address order, but they differ in the amount of information they include from each instruction.

full hash

  This hash includes the mnemonic and some of the addressing mode information from an instruction. Specific register operands are also included as part of the hash, but the specific value of constant operands are not.

specific hash

  This hash includes everything used in the full hash but may also include the specific values of any constant operands. A heuristic is employed that attempts to determine if the constant is not part of an address, in which case the value is accumulated into the hash.

Both hashes are used to identify matches in a database. The full hash is robust against changes due to linking; the specific hash helps distinguish between closely related variants of a function.

#### Parents and Children

When Function ID examines a function, its parent and child functions are also considered as a way of disambiguating multiple matches. For example, suppose two functions have identical sequences of instructions, except they each call to a different subfunction. In this situation, the full hashes of the functions will be identical, but the system will try to match the hash of one of the two subfunctions, allowing it to distinguish between the two.

#### Libraries

Within a Function ID database, functions are grouped into libraries, which are intended to be recognizable named software components that get linked into larger programs. A Library has the following meta-data.

Name

  This is a general descriptive name for the library.

Version

  If there is a formal version number for the library, this field will hold this value as a string.

Variant

  Version information that cannot be encoded in the formal Version field can be encoded in this field. This is used typically for compiler settings, which affect Function ID hashes but don't make sense in a version string describing the source code.

Generally, the analyzer is able to report all three fields describing the library for any function match it finds. In the case where a database contains multiple versions of the same library, it's common for a function to match into two or more libraries that differ in their Version or Variant field. In this case, the analyzer will still report a single match but will leave off the fields it couldn't distinguish.

#### Single Matches

A Single Match for a function occurs under the following conditions:

- The analyzer can narrow down potential matches to a single function name.
- The function does not already have an imported or user-defined name.
- The number of instructions in the function exceeds the instruction count threshold.

Even if there are multiple potential matches in the database, the first condition may still hold because they all share the same base function name. The second condition does not need to apply if the "Always apply FID labels" option is toggled on (See ). The number of instructions is computed as the match score and can include counts of instructions in parent or child functions. For details about the match score and thresholds, see .

If there is a Single Match, the analyzer will:

1. Apply the function name as a symbol.
2. Insert a comment describing the matching library.
3. Add a Function ID Analyzer bookmark.

Both the inserted comment and bookmark will include the phrase "Single Match".

#### Multiple Matches

If the analyzer is not able to narrow down to a single function name, even after applying all of its disambiguation logic, then the reporting behavior depends on the remaining match scores. If they are too small the matches are deemed to be random, and nothing is reported at all. Otherwise, a Multiple Match is reported. In this case, multiple symbols and comments will be inserted, one for each remaining match, up to an arbitrary limit. All the comments will contain the phrase "Multiple Matches".

### Analysis Options

This analyzer appears under the heading Function ID in the dialog listing the standard analyzers whenever the user elects to auto-analyze a new program upon import, or by selecting Auto Analyze under the Code Browser's Analysis menu. From this dialog, users can toggle whether the analyzer is active or not, and if Function ID is selected and toggled on, the dialog presents some configurable options for the analyzer.

Instruction count threshold

  This is the primary threshold a potential match must exceed in order to be reported by the analyzer. This defends against false positives caused by randomly matching small functions. Roughly, the score counts the number of instructions in the function plus instructions in any matching parent or child.

Multiple match threshold

  In general for a single function, if there are multiple potential matches all with different names, this is a good sign that the matches are random, and the analyzer will not report a match. But if the match score exceeds this threshold, the analyzer will report a Multiple Match. (See )

Always apply FID labels

  If this toggle is on, the analyzer will report matches even if there is already an imported or user defined name for the function.

Create Analysis Bookmarks

  The analyzer will only create bookmarks for matches if this toggle is on. This does not affect insertion of comments and symbols.

### Scoring and Disambiguation

The Function ID analyzer assigns a match score to each of the potential matches it discovers in its database. The score is used both to filter matches which are too small to be significant and to disambiguate between potential matches.

The basic unit of the score is a single matching instruction with no constant operands, which receives a score of 1.0. Certain instructions, such as calls and no operation instructions are assigned a score of zero. Constant operands, in the rare case that they match via the specific hash, contribute an additional 0.67 units per operand.

Once a potential match is discovered, it is assigned a score based on:

- Instructions in the body of the function.
- Constant operands that match in the body of the function.
- Instructions in the body of any child function that also has a match.
- Instructions in the body of any parent function that also has a match.

Once scores are assigned, potential matches are filtered based on the instruction count threshold (See ). This helps prevent small functions that randomly match database entries from being reported. Note however that a small function can still be correctly reported if its parent or child functions also have matches, increasing its overall score. If there are still more than one potential match, the highest assigned score is used to filter out matches with lower scores.

#### Matching Function Names

If there are still multiple potential matches once thresholds have been applied to the match scores, the remaining matches will be grouped based on function names. If two potential matches share the same function name, they are grouped together. If the remaining matches can all be placed into a group sharing a single name, the result will still be reported as a "Single Match".

Function names are considered to match if their base names match. The base name is obtained by stripping off any namespace from the symbol plus any initial underscores. If the name is mangled, an attempt is made to demangle it first, then namespace and parameter information is stripped.

## Function ID Plug-in

The Function ID Plug-in allows users to create new (.fidb) databases. A Function ID database is a collection of meta-data describing software libraries and the functions they contain. It is searchable via a hash computed over the body of unknown functions (See ). The databases are self-contained and can be shared among different users. Using this plug-in, databases can be created, attached, and detached from an active Code Browser, and a database can be populated with function hashes from programs in the current Ghidra project.

A Function ID database may hold many distinct libraries. Within a single library, all functions must come from the same processor model as determined by Ghidra's Language ID. Ideally, functions should come from a single software component, all compiled using the same compiler and settings.

Functions for a single library can be ingested from multiple files, usually from a series of object files analyzed within a Ghidra repository. If the library is spread across multiple files, accurate symbol information is necessary to properly compute parent/child relationships.

### Enabling the Plug-in

All plug-in functionality is accessible from the Function ID menu, under the main Tools menu. In order to access this menu, the tool must be configured to include the Function ID plugin. To do this, from the Code Browser select File -> Configure Then click on the Configure link under the Ghidra Core section and check the box next to "FidPlugin".

### Plug-in Functionality

The Function ID plug-in provides the following actions under Tools -> Function ID.

#### Choose active FidDbs...

This brings up a dialog that allows the user to select which Function ID databases are active. By default, Ghidra ships with a set of databases and they are all initially active.

Once a database has been deactivated, it will no longer be used for matches in subsequent analysis. The selections for which databases are active are saved as a preference on a per-user basis.

#### Create new empty FidDb...

This brings up a file chooser dialog that allows the user to create a new Function ID database. This cannot be located under the Ghidra install directory root, because Ghidra considers files under the root read-only. We recommend ending this database with the extension .fidb for consistency, although not strictly necessary. Newly created databases are attached (which means "known" for the purposes of tracking) and initially active, even though they contain no match entries.

#### Attach existing FidDb...

This brings up a file chooser dialog that allows the user to attach an existing Function ID database. This cannot be located under the Ghidra install directory root, because Ghidra considers files under the root read-only. Attached databases are saved in the user preference system, and retain their active status across sessions of Ghidra.

#### Detach attached FidDb...

This brings up a dialog that allows the user to detach an already-attached Function ID database. None of the databases delivered with Ghidra can be detached; they can only be deactivated (see ). Detaching a database removes it from use in searching, and also causes the user preference system to forget about the existence of this database.

#### Populate FidDb from programs...

Once a database has been created (or attached), the user may populate it with hash values from a set of programs in the current project. Choosing this option brings up a dialog where users enter the information needed to populate the database.

##### Dialog Fields

Fid Database

  Pick the database to populate. Users must select from attached databases that are writable.

Library Family Name

  The name of the library being ingested. This is the identifier that will be inserted as part of the comment when a match is found for functions in this library.

Library Version

  The formal version string for the library. This is frequently the <major>.<minor>.<patch> syntax but can be anything provided to distinguish between different versions of the same library.

Library Variant

  Any other string for distinguishing libraries that doesn't fit in the formal Version string. This frequently holds compiler settings.

Base Library

  This is an optional setting for cross-linking with an existing library already ingested in the database. In the event that the user wants to incorporate parent/child relationships into this library from another related library, they can set this option to point at the other library. The library must already be ingested (from a previous use of this command) into the same database. The Function ID ingest process will match parents and children across the libraries via function symbols.

Root Folder

  This specifies the set of programs from which the new library will be populated. The user can select any subfolder in the current Ghidra project. The ingest process will recursively search through all programs beneath this folder and, for each program, will collect any functions it contains.

Language

  This is the required 4-field Ghidra Language ID (i.e. x86:LE:64:default) specifying exactly what processor the new language will contain. While scanning during ingest, any program that does not match this program model will be automatically skipped.

Common Symbol File

  This is an optional parameter that provides a list of common function symbols to the ingest process. The parameter, if present, is a path to a text file that contains the list of function symbols, one per line. The ingest process excludes these functions from consideration as disambiguating child functions. (See )

Once all fields have been filled, clicking OK causes all selected functions to be ingested for the new library. Depending on the number of programs and functions selected, this process may take some time. Upon completion, the process will present a summary window, containing ingest statistics and an ordered list of functions that were most commonly called within the library. This list can be used to create a Common Symbol File tailored for the library.

### Preparing Libraries for a Function ID Database

#### Location of Programs

All functions going into a single Function ID Library must already be imported and analyzed somewhere within a single Ghidra repository (shared or non-shared). Multiple libraries contained within the same database can be ingested in different phases, but a single library must be written to the database in a single pass. The ingest dialog (see ) specifies a single subfolder as the root for the library. The process acts recursively, so there can be additional directory hierarchy under the root, but all programs to be included in the library must be under the one root.

#### Analysis

All programs must be analyzed enough to have recovered the bodies of all the functions that are to be included in the library. Generally, the easiest way to accomplish this is to run Ghidra's default auto-analysis. If functions are spread across multiple programs, as is typically the case, users can run the Ghidra's `analyzeHeadless` command to analyze across the whole set. However, take note below of some of the modifications to the default analysis that may be necessary to get good Function ID results.

Every function to be included must have a non-default function name assigned. Function ID uses a function's primary symbol for the name. Symbols are typically imported from debug information, but any method for assigning names, script based or manual, will work. Any function that still has its default name, `FUN_00....`, currently will not be ingested.

When performing auto-analysis in preparation for ingest, its best to disable the Function ID analyzer (and the Library Identification analyzer as well) in order to avoid cross contamination from different databases. If the function symbols are mangled, be sure to turn off the Demangler analyzer. This lets the future database apply the raw mangled symbol to new programs during analysis, which lets their Demangler analyzer pass run with complete information.

For an example of these sorts of modifications to the analysis process, see the file: `Features/FunctionID/ghidra_scripts/FunctionIDHeadlessPrescript.java` This is designed to be passed to the `analyzeHeadless` command as a pre-script option.

### False Positives

A false positive in the context of Function ID is a function that is declared as a match by the analyzer but has the incorrect symbol applied. As with any classification algorithm, it is generally not possible to eliminate this kind of error completely, but with Function ID there are some mitigation strategies.

#### Causes

False positives for the most part only happen with small functions. There are two related causes with Function ID:

Tiny Functions

  If a function consists of only a few instructions, it can be matched randomly if there are enough entries in the database. The fewer operations a function performs, the more likely an unrelated function is to do those exact same things.

Code Idioms

  A set of functions that are effectively identical can have different names and be used in unrelated contexts. Functions such as destructors are typical: one might check that a particular structure field is non-zero, and then pass that field to `free`. Another destructor may perform the exact same sequence, but was designed for a completely unrelated structure.

In either case, Function ID can apply a symbol that is misleading for the analyst.

#### Mitigation via Threshold

All mitigation strategies, to some extent, trade-off false positives for false negatives, which are functions that should have been reported by the Function ID analyzer, but aren't (because of some threshold or strategy).

Most false positives by far are due to tiny functions. Function ID minimizes these via the instruction count threshold. Potentially matching functions with too few instructions that don't exceed this threshold will simply not be reported by the analyzer.

For users experiencing too many false positives, the instruction count threshold is the easiest thing to adjust. It is fully controllable by the user as an Analysis option (See ), and increasing it will directly reduce the false positive rate, at the expense of missing some true matches whose scores now fall below the threshold.

#### Specialized Mitigation

The default instruction count threshold is a good starting point for any new database, generally striking a reasonable balance limiting false positives without eliminating too many true matches. But even for an optimal threshold, there may be a small handful of functions in the new database (usually Code Idioms) that exceed the threshold and repeatedly cause the wrong label to be placed. Instead of increasing the threshold to filter out all functions with these higher scores, it is possible to turn on one of several mitigation strategies that target the offending database entries directly. These strategies include:

Force Specific

  If this is set on an entry, the specific hash must match before the system will consider the entry as a potential match. This is useful when a code idiom contains a known constant that the full hash would usually miss.

Force Relation

  This is probably the most useful specialized strategy. It forces at least one parent or child match to be present before the system considers the base function as a potential match. So even if an idiom is big, this forces a search for an additional confirmation.

Auto Fail

  This is a strategy of last resort. If an obnoxious code idiom can't be eliminated any other way, this forces the particular database entry to never be considered as a match.

Auto Pass

  This strategy is different from the others, in that it applies to function entries whose scores are slightly too low. If a low scoring function has an instruction sequence that is deemed unique enough, this strategy causes any potential match to automatically pass the threshold. This provides an alternative to lowering the instruction count threshold to include a particular function.

These strategies can all be toggled for individual function records in the database. To do this manually from the Code Browser, the user needs to search for the specific records they want to change using the Debug Search Window and then make changes from its Result Window. For details see .

Strategies can also be toggled by running a Ghidra script. Within a script the basic instruction sequence looks like:

    FidFileManager fidFileManager = FidFileManager.getInstance();
    List<FidFile> allKnownFidFiles = fidFileManager.getFidFiles();
    // Choose a modifiable database from the list
    ...
    // Open a specific database
    FidDB modifiableFidDB = fidFile.getFidDB(true);

    // Toggle strategies based on the full hash of the function(s)
    modifiableFidDB.setAutoFailByFullHash(0x84d01243dfb8b9cbL, true);
    modifiableFidDB.setForceRelationByFullHash(0x4e0920960b48ae7eL, true);
    modifiableFidDB.setForceSpecificByFullHash(0x5ef2f47ee7151243L, true);
    modifiableFidDB.setAutoPassByFullHash(0x96a4a6fd5694523bL, true);
    ...
    // Save and close the database
    modifiableFidDB.saveDatabase("comment", monitor);
    modifiableFidDB.close();

FunctionID hashes for specific functions can be obtained with the `FIDHashCurrentFunction` script.

## Function ID Debug Plug-in

The Function ID Debug Plug-in allows users to inspect the individual records in a Function ID database. This functionality is generally only useful to users building their own databases. Users can look up individual records based on name or hash, but currently the plug-in is not capable of modifying records. The only exceptions are the strategies, which can be modified using the .

### Enabling the Plug-in

The Debug Plug-in adds options to the Function ID menu, under the Code Browser's main Tools menu. These options are in addition to those introduced by the , which uses the same menu. In order to access the Debug options, the plug-in must be enabled. To do this, from the Code Browser select File -> Configure Then click on Configure link under the Developer section and check the box next to "FidDebugPlugin".

### Plug-in Functionality

The Function ID Debug Plug-in introduces the following actions to the Tools -> Function ID menu.

#### Create Read-only Database

Users can convert the read/write (.fidb) database into the a read-only (.fidbf) form. This is the more efficient final form used directly by the Function ID analyzer. The .fidbf form is uncompressed on disk and the analyzer can use it directly, where the .fidb form must be converted before use.

#### Debug Search Window

This action brings up a Search dialog for the currently active Function ID databases. The text entry fields correspond to the individual fields in a function record that can be searched. If the variant Debug Search Window (Current Function) is invoked, the same dialog is brought up, but the Full Hash and the Specific Hash fields are pre-populated with hashes corresponding to the function at the current address.

A search is initiated for a specific search field by entering a value and then hitting the `RETURN` key, with the cursor and focus still in the desired field.

##### Search Fields

Function ID

  This is the internal row ID for function records in the database.

Name

  This searches through function names. Searches here will match any record whose name contains the search string.

Domain Path

  This searches through domain paths. A domain path is the file path, relative to the project root, of a program containing the function described by a particular record. Searches here will match any record whose domain path contains the search string.

FH

  This searches for records matching the full hash. The text field expects a 64-bit value. The hash can be entered as a hexadecimal string by prepending with "0x".

XH

  This searches for records matching the specific hash. The text field expects a 64-bit value. The hash can be entered as a hexadecimal string by prepending with "0x".

##### Result Window

Invoking a search will bring up the Result Window, presenting a row for each matching function record. Columns list properties of the function and correspond to the search fields described above. In addition to these, each record/row lists a few other columns:

Library

  This is the library containing the function

Code Unit Size

  This is the number of (scoring) instructions in the function's body. See .

Spec. + Size

  This is the number of distinct constant operands fed into the specific hash.

Warn

  This lists any special properties that have been toggled for the particular record. The column is presented as a string of single character codes, corresponding to each possible property. Properties include the mitigation strategies described in .

  - F - Auto Pass: The record automatically fails.
  - P - Auto Fail: The record automatically passes.
  - S - Force Specific: Specific hash must match for record to be considered.
  - R - Force Relation: A parent or child must match for record to be considered.
  - U - The function body was unterminated (analysis error).

###### Edit Menu

The Result Window supports a small number of actions under the Edit menu that allow the user to change the mitigation strategies for a read/write database. Strategies are described in . When a menu action is invoked, all records displayed in the current Result Window are affected. Currently there is no way to select a subset of records to effect. The actions all set or clear a specific strategy.

Set/Clear auto-fail

  Toggle the Auto Fail strategy.

Set/Clear auto-pass

  Toggle the Auto Pass strategy.

Set/Clear force-specific

  Toggle the Force Specific strategy.

Set/Clear force-relation

  Toggle the Force Relation strategy.

Save changes

  Changes made using the Edit menu are not immediately saved back to the underlying database until this action is invoked.

#### Table Viewer

This invokes an extremely low-level view into the underlying tables that back a Function ID database. It can be invoked on any attached database. A window is brought up that lists individual records in one table. A drop-down menu allows the user to switch between the different underlying tables. Most of the columns contain row keys and don't present readable values. The only meaningful table is likely to be the Libraries Table which will list each library making up the database.