The NDIS Packets Capture Driver


1. Introduction

The NDIS Packets capture Driver is a driver that acquires from the network hardware the packets transiting in the network and passes them to the programs that ask for them. An application can have access to our capture driver like to a file, and can read from it the data coming from the network. The Packets capture Driver uses the services provided by NDIS to communicate with the network adapters present on the machine. It has the ability to:

The driver was expressly created to support WinDump minimizing the differences from TcpDump. For this reason, writing the driver we tried to follow the design of the BSD Packet Filter (BPF).

FULVIO. Alcune note:

1. quello che dici nell'introduzione l'hai gia' detto da altre parti e mi sembra sostanzialmente superflua qui.

2. non e' vero che il driver e' stato creato per windump. E' stato creato per le libpcap, come un driver a basso livello per poter interfacciarci sopra delle librerie standard di cattura.

3. Non e' assolutamente chiaro il rapporto che c'e' tra driver, bpf, etc etc, e questo e' una eredita' del precedente capitolo. Adesso non mi puoi iniziare cosi' di brutto con i "BPF in UNIX" senza aver inquadrato BENE dove diavolo sono nell'architettura generale.

 

2. BPF in Unix

BPF, or BSD Packet Filter, described in [McCanne and Jacobson 1993], is a kernel architecture for packet capture proposed by Steven McCanne and Van Jacobson. It was created to work in UNIX kernel and exports services used by TcpDump and many other UNIX network tools. BPF has two main components: the network tap and the packet filter.

2.1. The network tap

The network tap collects copies of packets from the network device drivers and delivers them to listening applications. The incoming packets are put in a buffer, and are passed to the application when it’s ready to get them. Since a process might want to look at every packet on a network and the time between packets can be only a few microseconds, it is not possible to do a read system call per packet and BPF must collect the data from several packets and return it as a unit when the monitoring application does a read. To maintain packet boundaries, BPF encapsulates the captured data from each packet with a header that includes a time stamp, length, and offsets for data alignment.

2.2. The packet filter

The filter decides if a packet should be accepted and copied to the listening application. Most applications using packet capture facility reject far more packets than they accept and, thus, good performance of the packet filter is critical to good over-all performance. (FULVIO Ehhh? Cosa volevi dire?) A packet filter is simply a function with boolean output that is applied to a packet. If the value of the function is true the kernel copies the packet for the application; if it is false the packet is ignored. Historically there have been two approaches to the filter abstraction: a boolean expression tree and a directed acyclic control flow graph or CFG. More details about them can be found in [McCanne and Jacobson 1993]. These two models of filtering are computationally equivalent, i.e., any filter that can be expressed in one can be expressed in the other. However, in implementation they are very different: The tree model maps naturally into code for a stack machine while the CFG model maps naturally into code for a register machine. BPF creators choose CFG because it can be implemented more efficiently on modern computers, that are register based. The BPF pseudo-machine abstraction consists of an accumulator, an index register (x), a scratch memory store, and an implicit program counter. It is able to execute load and store instructions, branches, arithmetic instructions and so on. Therefore, a UNIX application like TcpDump that wants to set a filter on the incoming packets, builds a program for the pseudo-machine and sends it to BPF. BPF executes the filter program on every packet and discards the ones that don’t satisfy the filter. The BPF pseudo-machine has some nice features:

FULVIO. Ottima e concisa descrizione del BPF. Manca:

1. dove il BPF e' piazzato (tanto per riperterlo ancora un'altra volta)

2. che rapporto c'e' tra buffering e bpf. Sono due cose separate? SOno insieme nell'architettura?

 

3. Interaction with NDIS

NDIS is a set of specifics that defines the communication between a network adapter (or, better, the driver that manages it) and the software that implements the various protocols (IP,IPX...). According to the terminology of NDIS, the drivers that pilot the network adapters are called network drivers, while the drivers that implement the protocols are called protocol drivers. NDIS supports multiple network drivers and multiple protocol drivers. Each protocol driver exports a set of functions that NDIS will call when to create a communication between a network driver and that protocol driver. Our packet driver is for NDIS a standard protocol driver: it has a callback function called PacketReceiveIndicate that NDIS invoke every time a new packet arrives. The behavior of the packet driver is however quite different from the one of a standard protocol driver. In fact:

Note that in UNIX implementation, BPF is called before the protocol stack, directly by the network interface’s driver. This is not possible for our driver, that is a part of the protocol stack and is called by NDIS. Obtaining the precedence would imply changes in the kernel, which is not possible in Windows.

FULVIO. QUin manca decisamente una descrizione non dico approfondita, ma almeno "corposa" di come e' fatto NDIS, quali sono le differenze principali tra le varie versioni, che versioni sono implementate in che OS. Questo e' necessario per capire:

- quali erano i posti dove potevamo agganciare il network packet driver e perche' l'abbiamo agganciato dove e' ora

- le differenze, a livello di itnerazione driver - ndis, tra i vari sistemi operativi (credo che questa sezione manchi proprio un po' del tutto).

mi sta bene l'interazione con NDIS, ma NDIS cos'e'?

Ricorda sempre che quello che stai facendo adesso con la documentazione e', pedestre pedestre, scrittura di capitoli dit esi. Quindi non vederlo come un lavoro inutile.

E' evidente che la trattazione di NDIS dovrebbe essere messa circa all'inizio; in altre parole sarebbe un po' da ripensare il precedente capitolo introduttivo. Secondo me capitolo introduttivo vuol dire "spiegare le cose che stanno attorno al nostro progetto, che sono servite per portarlo a termine, ma che non sono direttamente opera nostra." In base a questa idea, nel capitolo introduttivo dovrebbero starci (occhio e croce):

- i bpf

- ndis

- architettura generale del paccone, in relazione ai blocchi fondamentali esistenti, e che sono appena stati sviscerati.

 

4. Structure of the driver

For the development of the NDIS Packet Driver we started from the packet example provided with the Windows Device Driver Kit (DDK). It provides the basic structure of a network capture driver, useful as example and starting point, but has unacceptable performance and speed limitations. Substantial changes had to be made to obtain a behavior good enough for a serious capture application. We implemented a structure compatible with BPF to make simpler the porting of TcpDump and libpcap. (FULVIO: lascia stare windump. Windump e' una logica conseguenza del porting di libpcap, e potremmo portare anche altre applicazioni, non solo windump). The result is a packet driver that can:

Note that not all UNIX systems have BPF in the kernel. TcpDump can run on systems without BPF, (FULVIO: sensa BPF? E che lo fa il filtraggio?) doing at user level all the work that BPF usually does in the kernel. This solution was adopted by the version 1.0 of the packets capture driver, that was very small and simple, but had very poor capture performances, for the reasons seen in chapter 1.

Therefore, from version 2.0 the packet capture driver includes filtering and buffering capabilities like BPF.

 

4.1. Basic architecture and differences between the various versions

The basic structure of the driver is shown in Figure 2.1.

 

pic3.gif (5110 byte)

                         Figure 2.1: structure of the driver

 

The arrows toward the top of the picture represent the flow of the packets from the network to the capture application. The bigger arrow between the buffer and the application indicates that more than one packet can transit between these two entities in a single call. The arrows toward the bottom of the picture indicate the path of the packets from the application to the network. WinDump and libpcap do not send packets to the network, therefore they use only the path from the bottom to the top. The driver however is not limited to the use with WinDump and can be used to create new network tools. For this reason it has been included the possibility to write packets, that can be exploited through the packet.dll API.

The structure shown in Figure 2.1 is the only possible in Windows 95/98, because the Windows 95 version of the driver can have only a running instance. This means that the user will not be able to run more than one capture program at the same time. This is due to limitations in the architecture of the current version.

The structure of the Windows NT version of the packet capture driver is more complex and can be seen in figure 2.2. This figure shows the driver's configuration with two network adapters and two capture applications.

 

pic4.gif (6430 byte)

Figure 2.2: structure of the driver with two adapters and a two applications

 

For every connection between an adapter and a capture program, the driver allocates a filter and a buffer. The single network interface can be used by more than one application at the same time. For example a user that wants to capture the IP and the UDP traffic of a network and save them in two separate files, can launch two sessions of WinDump at the same time. (FULVIO: ho aggiunto che la versione 95 non supporta piu' sessioni contemporanee, nelle FAQ) The first session will set a filter for the IP packets (and a buffer to store them), and the second a filter for the UDP packets. Note that the system resources needed by the use of two WinDump sessions configured in this way will be approximately the same that will be requested by a single WinDump application with a filter configured to accept both the IP and the UDP packets. In fact in the configuration with two WinDump sessions, the driver must calculate two filters (instead of one) for every incoming packet, but they are simpler (so lighter and therefore faster to calculate). Furthermore, the driver’s buffer needed by the two instances of the driver in the configuration with two WinDump sessions will be smaller because it will contain a smaller number of packets. The number of packets sent by the driver to the user level is instead exactly the same in the two situations.

FULVIO: non e' chiarissimo. INoltre esiste anche il costo della copia in memoria. QUindi se il numero di paccektti catturati e' diversi il load e' diverso.

Altra cosa: non hai mai parlato di pacchetti bufferizzati sulla scheda e persi. Anche questo puo' capitare: il pachetto viene ricevuto dalla scheda, ma la CPU non e' abbastanza veloce per cui non serve l'interrupt e il pacchetto viene sovrascritto. Credo che, con le moderne CPU, il rischio sia ridotto, pero' bisognerebbe fare almeno un cenno a qs problema.

 

In Windows NT it is also possible for a single application to receive packets from more than one interface, opening a different driver instance on each network adapter.

FULVIO: e cosa succede se apro piu' istanza di windump sullo stesso adapter? Su UNIX funziona. E qui?

If we don’t consider the differences just described, the Windows 95 and Windows NT versions are quite similar. The internal data structure are not very different, the buffer and the filter are handled in the same way. The interaction with NDIS is very similar in the two platform and is obtained by a set of callback functions exported by the driver and a couple of functions (NdisTransferData, NdisSend...) used to retrieve and send the packets. What is different is the interaction with the operating system (handling of the read and write calls, time functions...), since the philosophy of the two operating systems is quite different.

FULVIO: e' un po' stitico, la parte del confronto95/NT...

4.2. The filtering process

The filter mechanism present in the NDIS packet capture driver derives directly from the BPF filter for the UNIX platform, therefore all the things said about the BPF filter are valid for the filter of the driver. An application that needs to set a filter on the incoming packets can build a standard BPF filter program (for example through a call to the libpcap’s pcap_compile function) and pass it to the driver, and the filtering process will be done in kernel mode. The BPF program is transferred to the driver through an IOCTL call with the control code set to pBIOCSETF. A very important thing is that the driver needs to be able to verify an application's filter code. In fact, as we said, the BPF pseudo-machines can execute arithmetic operations, branches, etc. A division by zero or a jump to a forbidden memory location, if done by a driver, bring inevitably to a blue screen. Therefore, without protection, a buggy or bogus filter program could easily crash the system. Since the packet capture driver can be used by any user, it could be easy for an ill-intentioned person to cause damages to the system using it. For this reason, every filter program coming from an application must be checked by the driver before being accepted. If a filter is accepted, the driver executes the filter program on every incoming packet, discarding the ones that don’t satisfy the filter’s conditions. If the packet satisfy the filter, it is copied to the application, or put in the buffer if the application is not ready. If no filter is defined, the driver accepts all the incoming packets.

A very nice feature of the BPF filter exploited by the packet capture driver is the use of a numeric return value. When a filter program is applied to a packet, the BPF pseudomachine tells not only if the packet must be trasnferred to the application, but also the length of the part of the packet to copy. This is very useful when the packet capture driver is used by a monitor application or by a network analyzer. Usually, this kind of applications needs only the header, that is the first part of the packet, and not the data contained in the packet. It is possible (and recommended) for these applications to set a filter to capture only the header of the packets. With such a filter, the driver will save in the buffer and copy to the application only the first part of each packet, improving the capture speed and decreasing the probability of having any packet dropped.

FULVIO Qui dici "improving the capture speed" ma secondo me non e' chiaro (dai paragrafi precednenti) che anche la copia in memoria ha un costo, e si tratta di limitarla il piu' possibile. Tra il resto io mi chiedo sempre: ma quante volte la memoria viene allocata per ogni singolo pacchetto?

The source code of the filter derives from the bpf_filter.c file in the libpcap distribution. This file contains two main functions: bpf_filter and bpf_validate.

4.3. The buffering process

Simplifying, when an application wants to obtain the packets from the network, it performs a read call on the NDIS packet capture driver. This call can be synchronous or asynchronous, because the driver offers both the possibilities. In the first case, the read call is blocking and the application is stopped until a packet arrives to the machine. In the second case, the application is not stopped and must check when the packet arrives. The usual and RECOMMENDED method to access the driver is the synchronous one, because the asynchronous one is difficult to implement and can bring to errors. WinDump uses only the synchronous method, and all the considerations that we will make apply only to the synchronous method.

After an incoming packet is accepted by the filter, the driver can be in two different situations:

The driver uses a circular buffer to store the packets. the size of the buffer at the beginning of a capture is 0. It can be set or modified in every moment by the application through an IOCTL call. When a new dimension is set, the packets currently in the buffer are lost. If the buffer is full, the incoming packet is discarded. The dimension of the driver’s buffer affects HEAVILY the performances of the capture process. In fact, it is likely that a capture application, that needs to make operations on each packet, sharing at the same time the processor with other tasks, will not be able to work at network speed during heavy traffic or bursts. This problem is more noticeable on slower machines. The driver, on the other hand, runs in kernel mode and is written expressly to capture the packets, so it is very fast and usually it does not loose packets. Therefore, an adequate buffer in the driver can store the packets while the application is busy, compensate the slowness of the application, and can avoid the loss of packets during bursts or high network activity. 

If the buffer is not empty when the application performs a read call, the packets in the buffer are copied in the application memory by the driver and the read call is immediately completed. More than one packet can be passed to the application with a single read call. This improves the performances because it minimizes the number of read. Every read call in fact involves a switch between the application and the driver, i.e. between user mode (ring 3 on Intel machines) and kernel mode (ring 0). Since these context switches are quite slow, decreasing their number means improving the capture speed. To maintain packet boundaries, the driver encapsulates the captured data from each packet with a header that includes a timestamp and length. The application must be able to properly unpack the incoming data. The data structure used to perform the encapsulation is the same used by BPF in the UNIX kernel, so the format of the data returned by the driver is the same returned by BPF in UNIX.

BPF in UNIX performs a further optimization, aligning the packet data in memory in a way that minimizes the overhead of the copy process. The NDIS packet capture driver doesn’t implement this feature yet.

 

4.4. Other functions