Static analysis "BIOS / UEFI" or how to get Dependency Graph

"I finished forging yesterday, I have made two plans ... " ... VS Vysotsky song ...

Already almost 3 years ago (at the beginning of 2016), in the UEFITool project issue on GitHub, the wish of users appeared: to build a “Dependency Graph” for executable modules included in the BIOS / UEFI.

Even a small discussion ensued, as a result of which it finally became clear that this task is by no means trivial, the existing functionality for its solution is not enough, the prospects are vague at that moment ...

And this question remains in limbo, with the prospect of implementation in an uncertain future (but the desire probably remains, and hope, as is known, dies last!).

There is a suggestion: to find, finally, a solution to this problem!

We define the terms

In the following, it is assumed that we are dealing with Intel 64 and IA-32 Architecture.

In order to unequivocally decide what we decided to build, we will have to deal in more detail with the functioning of the individual phases of the BIOS / UEFI operation.

If you look closely at the file types represented in the FFS firmware volumes, it turns out that most of the available files have a section with executable modules.

Even if we look at ASUS or ASRock modern firmware, in which you can easily find up to one hundred and fifty files of type EFI_FV_FILETYPE_FREEFORM containing images of different formats, however, even in these firmware there are more executable files than other files.

+--------------------------------------------------------------------------+ | File Types Information | +--------------------------------------------------------------------------+ | EFI_FV_FILETYPE_RAW = 6 | | EFI_FV_FILETYPE_FREEFORM = 83 | | EFI_FV_FILETYPE_SECURITY_CORE = 1 | | EFI_FV_FILETYPE_PEI_CORE = 1 | | EFI_FV_FILETYPE_DXE_CORE = 1 | | EFI_FV_FILETYPE_PEIM = 57 | | EFI_FV_FILETYPE_DRIVER = 196 | | EFI_FV_FILETYPE_APPLICATION = 1 | | EFI_FV_FILETYPE_SMM = 60 | | EFI_FV_FILETYPE_SMM_CORE = 1 | | EFI_FV_FILETYPE_PAD = 4 | +--------------------------------------------------------------------------+ | Total Files : = 411 | +--------------------------------------------------------------------------+ 

An example of the composition of some conventional (ordinary) firmware.

Although in this table the files that have executable modules are not marked, nevertheless, they will be (by definition) everything in this list, except for files with suffixes RAW, FREEFORM and PAD.

Files with the suffix "CORE" (SECURITY_CORE, PEI_CORE and DXE_CORE) are the corresponding "cores" (the head modules of the corresponding phase) that receive control from other phases (or after the start), SMM_CORE is a sub-phase of the DXE-phase and is called during execution. APPLICATION can be performed only at the user's request, it does not have a specific binding to the phases.

The following common file types are not listed: PEIM (PEI-phase modules), DRIVER (DXE-phase modules) and SMM (DXE sub-phase modules). The CORE modules of the PEI and DXE phases include a dispatcher, which controls the loading / starting sequence of the modules of the corresponding phase.

In the above example, there are no combined options, we will not recall them: in real firmware, although they occur, they are quite rare. Those who wish to obtain more detailed and detailed information are invited to refer to the articles CodeRush 1 , 2 , 3 . We will also quote his advice: “For fans of original documentation, the UEFI PI specification is always available, everything is written in much more detail.”

Each executable firmware module is a PE + (Portable Executable) format module or a derivative of it (Terse Executable: TE-format). The PE + format executable module is a set of “slightly” packed structured data containing the information the loader needs to display this module in memory.

The PE + format itself (structure) does not have any interaction mechanism between individual PE + modules. Each executable module after loading and starting execution is an autonomous independent process, (well, it should be so!) , I.e. the module should not “assume” anything about what is being done outside it.

The organization of interaction between separate executable modules of a single UEFI phase is organized by means of a “CORE” module of the corresponding phase. Individual executable modules can define (Install) protocols, query (Locate) and use protocols declared by other modules, set / announce events, and declare (Notify) event handlers.

Thus, for each executable firmware module we are interested in the presence of the following artifacts:

1. List of protocols that this module defines. (Each protocol is identified by a unique number - guid).
2. List of protocols that this module uses (tries to use).
3. The list of events that this module announces. (The event has a unique number - guid).
4. List of event handlers present (implemented and can be installed / initialized) in this module.

Static Dependency Graph for a given phase of BIOS / UEFI is considered defined if for each executable module of a phase, we know all the artifacts listed above in items 1-4. (In other words, if we have defined all the information describing the interdependencies between the modules).

We will consider only the static analysis option, this means that some code elements that implement items 1-4 may be unreachable (they are fragments of the “dead” code) or will be reachable only under certain options of input data / parameters.

Everything that we have considered so far is based only on the BIOS / UEFI specification. And in order to understand the “relationships” of the available executable modules of the firmware in question, we will have to delve somewhat into their structure, and therefore, to take up at least a partial reversal of them (restoring the original algorithms).

As it was already written above, the PE + format executable module is just a set of structures for the loader, which builds in memory an object to which control will be transferred, and this object by its nature consists of processor commands, as well as data for these commands.

We will say that the executable module was completely disassembled , if it was possible to solve the task of separating the commands and data presented in this module.

At the same time, we will not impose any requirements on the structure and data types; it is enough if for each byte belonging to the executable module image received by the loader, we can unequivocally tell which of the two categories it belongs to: command byte or data byte.

The task of completely disassembling an executable module is generally not trivial, moreover, in the general case it is not algorithmically solvable. We will not go into the details of this question; we will not break spears either; we consider this statement as an axiom.

Suppose:

1. We have already solved the problem of complete disassembly for a specific BIOS / UEFI executive module, i.e. we managed to separate the teams and data.
2. There is a source code for the module in the “C” language (in the current BIOS / UEFI firmware, the modules are mostly developed in the “C” language).

Even in this case, simply comparing the results obtained (assembler text is just a textual representation of processor commands) with source texts in the C language will almost always require a strong experience / qualification, except absolutely degenerate cases.

A complete study of examples showing the difficulties of identifying or comparing the results of disassembling with the source code is not included in our current plans.
Consider only an example when, in the resulting assembler listing, we meet the “Indirect Call” command — an implicit procedure call.

This is an example of a procedure call referenced in the table. A table containing references to various procedures is a typical case of the implementation of an arbitrary protocol interface representation.

Such a table does not have to consist only of references to procedures, no one forbids storing simply arbitrary data in this structure (and this is an example of a typical “C” -shny structure).

Here is one of the forms of such a call (instead of the “ecx” register, almost all variants of the 32-bit processor registers are possible):

FF 51 18 call dword ptr [ecx + 18h]

Having got, as a result of the analysis, a similar command, it is possible to figure out what procedure is called, the list of its parameters, the type and value of the returned result, only if we know the type of the object (protocol) whose interface is invoked by this command.

If we know that in the previous example the register “ecx” contains a pointer (the address of the beginning of the table EFI_PEI_SERVICES), we can get (present) this command in the following more understandable and “pleasant” form:

FF 51 18 call [ecx + EFI_PEI_SERVICES.InstallPpi]

Obtaining information about the contents of the register participating in the “Indirect Call” team most often goes beyond the capabilities of a “typical” disassembler whose task is simply analyzing and converting the binary (binary) code of the processor into a human-readable form — a textual representation of the corresponding processor command.

To solve this problem, it is often required to use additional (Meta) information that is missing in the binary executable module (lost as a result of compilation and linking - it is used in converting from one algorithm representation to another, but is no longer needed by the processor to execute the received commands).

If this Metadata is still available to us from additional sources, then using them and conducting additional analysis, we get a more understandable (and more accurate) representation of the “Indirect Call” command.

Actually, this advanced analysis is more like the process of "decompiling", although the result does not look like the source text of the module in the "C" language, however, in the future we will call this process decompiling commands that are "Indirect Call" or " partial "decompilation .

So, we are ready to determine sufficient conditions for constructing the graph of the interdependence of executable firmware modules for the given BIOS / UEFI phase:

To obtain a Static Dependency Graph (either phase — PEI or DXE), it is sufficient to completely disassemble all the executable modules of the corresponding phase (at least separate all commands) and decompile the “Indirect Call” commands present in the disassembled modules.

Immediately, a lot of questions arise about how our knowledge of the “Indirect Call” teams is connected with inter-module interactions.
As mentioned above, the entire service for the organization of interaction is provided by the “CORE” module of the corresponding phase, and the services in the phases are arranged in the form of “basic” service tables.

Since the models of interaction between modules in the PEI and DXE phases, although ideologically (structurally) similar, are technically different, it is proposed to move from a few formal considerations to the consideration of a specific direct construction of the Static Dependency Graph for the PEI phase.

We even manage to define and formulate necessary and sufficient conditions for the possibility of constructing a Static Dependency Graph for the PEI phase.

Building a Static Dependency Graph for the PEI phase

Descriptions of the solution of the problem of complete disassembling of the executed PEI-phase modules and decompiling the “Indirect Call” commands present in these modules are beyond the scope of our narration and will not be included in it - the presentation of this material by itself may exceed the size of this opus.

It is possible that with time this will occur as a separate material, but for now - “know how”.

We only note that the involvement of Metadata, plus the presence of a certain structure for building a binary code, allows in practice to carry out a complete disassembly of executable BIOS / UEFI modules. Formal proof of this fact is not expected either now or in the future. At least when analyzing / processing more than a hundred (100) BIOS / UEFI from different manufacturers, there were no examples where complete disassembly could not be carried out.

Further, only specific results (with explanations: what, how and how much ...).

The EFI_PEI_SERVICES structure is the basic structure of the PEI phase, which is transmitted as a parameter to the entry point of each PEI module and contains references to the basic services that the PEI modules need to operate.

We will be interested only in fields located at the very beginning of the structure:



Fragment of a real structure of type EFI_PEI_SERVICES in the IDA Pro disassembler.

And this is how it appears in the source code in the “C” language (I remind you, this is only a fragment of the structure):

 struct EFI_PEI_SERVICES { EFI_TABLE_HEADER Hdr; EFI_PEI_INSTALL_PPI InstallPpi; EFI_PEI_REINSTALL_PPI ReInstallPpi; EFI_PEI_LOCATE_PPI LocatePpi; EFI_PEI_NOTIFY_PPI NotifyPpi; //...Ещё много ссылок на различные базовые сервисы... }; 

At the beginning of the EFI_PEI_SERVICES structure, as in all the “Basic” Services Tables, is the EFI_TABLE_HEADER structure. The values ​​presented in this header structure allow us to state unequivocally that the fragment from the disassembler actually has if not the EFI_PEI_SERVICES structure itself (see the “Hdr.Signature” field), then at least the template of this structure!

 struct EFI_TABLE_HEADER { UINT64 Signature; UINT32 Revision; UINT32 HeaderSize; UINT32 CRC32; UINT32 Reserved; }; 

Along the way, we can establish that the firmware was developed at the time when the version of the UEFI PI specification was 1.2, the validity period of which was from 2009 to 2013, but at the current moment (beginning of 2019) the current version of the specification has already grown (just recently it has grown) Up to version 1.7.

From the “Hdr.HeaderSize” field it can be determined that the total length of the structure is 78h (and this is by no means the length of the header, as the name implies, but the length of the whole EFI_PEI_SERVICES structure).

The EFI_PEI_SERVICES interfaces are divided into 7 categories / classes. We simply list them:

1. PPI Services.
2. Boot Mode Services.
3. HOB Services.
4. Firmware Volume Services.
5. PEI Memory Services.
6. Status Code Services.
7. Reset Services.

All further narration will directly relate to the procedures belonging to the category / class "PPI Services", designed to organize inter-module interaction of the executed modules of the PEI-phase.

And there are only four of them for the PEI phase.

In general, there is no need to guess about the purpose of each of the interfaces: the functionality is fully determined by the name of the interface, all the details are in the specification .

The following are the prototypes of these procedures:

 typedef EFI_STATUS (__cdecl *EFI_PEI_INSTALL_PPI)( const EFI_PEI_SERVICES **PeiServices, const EFI_PEI_PPI_DESCRIPTOR *PpiList); typedef EFI_STATUS (__cdecl *EFI_PEI_REINSTALL_PPI)( const EFI_PEI_SERVICES **PeiServices, const EFI_PEI_PPI_DESCRIPTOR *OldPpi, const EFI_PEI_PPI_DESCRIPTOR *NewPpi); typedef EFI_STATUS (__cdecl *EFI_PEI_LOCATE_PPI)( const EFI_PEI_SERVICES **PeiServices, const EFI_GUID *Guid, UINTN Instance, EFI_PEI_PPI_DESCRIPTOR **PpiDescriptor, void **Ppi); typedef EFI_STATUS (__cdecl *EFI_PEI_NOTIFY_PPI)( const EFI_PEI_SERVICES **PeiServices, const EFI_PEI_NOTIFY_DESCRIPTOR *NotifyList); 

We only note that in addition to the “Indirect Call” commands calling the “PPI Services” class procedures / interfaces, an explicit (direct — not tabular) call of these procedures is possible, which sometimes happens in executive modules where the EFI_PEI_SERVICES structure is defined / created.

I will reveal one small secret: oddly enough, even though this is the “base” table of services of the PEI phase, however, as practice shows, it can be defined not only in the PEI_CORE module.

In the real nature, there are firmwares in which the structure of the EFI_PEI_SERVICES was defined / formed and used in several modules, and these were not copies of the PEI_CORE module.

Thus, the following code options are possible:

 seg000:00785F0D B8 8C A6 78+ mov eax, offset ppiList_78A68C seg000:00785F12 50 push eax ; PpiList seg000:00785F13 57 push edi ; PeiServices seg000:00785F14 89 86 40 0E+ mov [esi+0E40h], eax seg000:00785F1A E8 70 FC FF+ call InstallPpi 

An example of an explicit call to the “InstallPpi” procedure.

 seg000:00787CBB 8B 4D FC mov ecx, [ebp+PeiServices] seg000:00787CBE 50 push eax ; PpiList seg000:00787CBF C7 00 10 00+ mov dword ptr [eax], 80000010h seg000:00787CC5 C7 43 3C A8+ mov dword ptr [ebx+3Ch], offset guid_78A9A8 seg000:00787CCC 8B 11 mov edx, [ecx] seg000:00787CCE 51 push ecx ; PeiServices seg000:00787CCF FF 52 18 call [edx+EFI_PEI_SERVICES.InstallPpi] 

An example of implicitly calling the InstallPpi interface.

 FF 51 18 call dword ptr [ecx+18h] FF 51 18 call [eсx+EFI_PEI_SERVICES.InstallPpi] FF 51 1С call dword ptr [ecx+1Ch] FF 51 1C call [eсx+EFI_PEI_SERVICES.ReInstallPpi] FF 51 20 call dword ptr [ecx+20h] FF 51 20 call [eсx+EFI_PEI_SERVICES.LocatePpi] FF 51 24 call dword ptr [ecx+24h] FF 51 24 call [eсx+EFI_PEI_SERVICES.NotifyPpi] 

Examples of implicit interface calls before and after identification.

We note one characteristic feature: in the case of the PEI phase for IA-32 architectures, the interfaces of the PPI Services class are offset (offset) 18h, 1Ch, 20h, 24h.

And now we state the following statement:

To build a PEI phase Static Dependency Graph , it is necessary and sufficient to completely disassemble all executable phase modules (at least separate all commands) and decompile the “Indirect Call” commands with offsets 18h, 1Ch, 20h, 24h in disassembled modules.

In fact, we have fully formulated the algorithm for solving the problem, and as soon as we managed to isolate all the interface / procedure calls of the PPI Services class, it remains only to determine which parameters are passed to these calls. The task may not be the most trivial, but, as practice has shown, completely solvable, we have all the data for this.

And now real examples of real data for real PEI-phase modules. Intentionally we do not indicate for which company / BIOS the results were obtained for the company, we simply give examples of what they look like.

Two examples of the description of PEIM-modules with full information about the use of "PPI Services" interfaces in these modules

  -- File 04-047/0x02F/: "TcgPlatformSetupPeiPolicy" : [007CCAF0 - 007CD144] DEPENDENCY_START EFI_PEI_READ_ONLY_VARIABLE_ACCESS_PPI DEPENDENCY_END Install Protocols: [1] TCG_PLATFORM_SETUP_PEI_POLICY Locate Protocols: [2] EFI_PEI_READ_ONLY_VARIABLE_ACCESS_PPI 

 -- File 04-048/0x030/: "TcgPei" : [007CD160 - 007CF5DE] DEPENDENCY_START EFI_PEI_MASTER_BOOT_MODE_PEIM_PPI EFI_PEI_READ_ONLY_VARIABLE_ACCESS_PPI AND DEPENDENCY_END Install Protocols: [1] AMI_TCG_PLATFORM_PPI [2] EFI_PEI_TCG_PPI [2] PEI_TPM_PPI Locate Protocols: [1] EFI_PEI_TCG_PPI [1] EFI_PEI_READ_ONLY_VARIABLE_ACCESS_PPI [1] TCG_PLATFORM_SETUP_PEI_POLICY [5] PEI_TPM_PPI Notify Events: [1] AMI_TCM_CALLBACK ReInstall Protocols: [1] PEI_TPM_PPI 

Lists of protocols by type of interface in which they were used

Below the spoilers are abbreviated examples of PPIM protocol lists for each of the interfaces of the PPI Services class.

The format of the lists is as follows:

 |  sequence number |  name_PPI |  guid_PPI |  executable module name: use_address |

The final list of all protocol guides that are referenced in a particular BIOS / UEFI with a legend indicating in which “PPI Services” these protocols are found

Below, under the spoiler is a list of 97 PPi-guid-s found and explicitly used in a specific firmware, the data for which were cited earlier.

Each element from the list is preceded by a legend reflecting all types of use of a particular protocol.

 "D" - in DEPENDENCY section used "I" - in "InstallPpi" functions used "L" - in "LocatePpi" functions used "R" - in "ReInstallPpi" functions used "N" - in "NotifyPpi" functions used 

In this BIOS / UEFI, the following protocol list intervals are noteworthy:

1. No. 38-50.
   Identification of protocols / events (InstallPpi) that are not used by any module.
2. №№ 87-95.
   Attempt to query protocols that have not been installed by any module of this firmware.
   
3. №№ 96-97.
   Two “Notify” events for which no module bothered to declare the corresponding interface, respectively, these procedures, though declared in executable modules, will never work.

Conclusion

• Results similar to those listed above were obtained for BIOS / UEFI from various manufacturers, which is why all examples are anonymous.
• In fact, the more general tasks of reversing the algorithms of executable BIOS / UEFI modules were solved, and the resulting graph was a side effect, a sort of additional bonus.

• The correct solution of the “Acquire Static Dependency Graph” task for BIOS / UEFI executable modules requires performing static binary code analysis, which includes carrying out a complete disassembly of executable modules and partial decompiling of the “Indirect Call” commands of these modules.