Note: this is a rough writeout of what will be presented at Uninet Infosec Infosec 2002 on Saturday, 20 April, 2002. A babelfish translation into spanish and french appears below. The slides are available on my website at: http://www.monkey.org/~jose/presentations/czech-rubicon02.d/ ... this page is available at http://www.monkey.org/~jose/presentations/czech-rubicon02.d/czech.html
INTRODUCTION
[slide 1]
This talk is designed to introduce the application of lexical analysis
to source code analysis. Specically, the design and implentation of the
static analysis tool for the C programming language, named "czech", will
be presented. Several inherent flaws in static analysis, the use of lexical
analysis in source code reviews, and specific lessons learned from the
failure in the implentation of czech will be discussed.
[slide 2]
Briefly, I will give an overview of some of the current research I am familiar
with in this arena. Several people are attempting to leverage many, many years
of source code evaluation methods and tools to automate security analysis of
their code. This is an area of high interest for corporate and academic
researchers alike. I will introduce what lexical code generation tools are and
how they operate, specically the use of the "flex" tool, a freely available
lex parser. I will then outline typical strategies for these tools, and then
delve into the specific challenges faced in the execution of the czech tool,
both for the tool and the author as well as for users of the tool.
[slide 3]
Quickly, an overview of the presentation specifically about czech. I will
discuss the design philosophy of czech, and then how I designed and then
executed the implementation. The performance of czech is something I'm quite
proud of, interestingly enough. I'll give some example of how it operates and
show you the rough output of the tool, and discuss some of the outstanding
bugs as it currently stands. Lastly, I will discuss some of the future
directions for czech and the whole of project pedantic.
[slide 4]
Despite all of the interest its getting these days, source code analysis is not
anything new. Software engineering researchers have been doing this for years.
In the security realm, this has become a hot area for researchers in recent
years, and many big groups have chimed in. These include David Wagner, David
Evans, and Microsoft.
The two big approaches are static analysis, looking at source code typically. Dynamic analysis, in constrast, takes the whole or parts of the program and runs it with varying input, monitoring the behavior of the program. Static analysis focuses on things like logical analysis of the design, flow analysis as it handles data, and the analysis of type qualifiers in arguments. All of these have their varying strengths, including the extendability, ease of use, or completeness of coverage.
It should definitely be noted that no method gives total coverage, and each misses some aspects. Also, there is the Turing 'halting problem', where you can only examine a small fraction of the possible states of the code in any given time frame. As such, you have to focus in on some aspects and make tradeoffs between completeness and efficiency.
[slide 5]
Project pedantic certainly owes a lot to some of the more accessible
static analysis tools. Pscan was one of the first format string analysis
tools, and could be used to find some common format string problems (see also
KF's talk later today for what those mean). ITS4, and later RATS, were also
some of the most commonly cited tools for common programming errors.
Both are also based on lexical analysis, too. Flawfinder, based on python,
works similarily to RATS, but makes some smarter decisions. Lastly, two
great tools to note are Lclint and splint, both from the research of
David Evans and coworkers in Virginia (USA).
Czech takes a lot of inspiration from these tools. In fact, I started writing it after a piece I wrote for Linux Journal on RATS, ITS4 and Flawfinder and getting rather upset with them. Also, during the design of czech, I spoke to David Wheeler, the author of Flawfinder. I tried to leverage a lot from this 'prior art'. I should also note, for humor's sake, that the test suite for czech breaks RATS and Flawfinder.
[slide 6]
Lex is a tool for parsing input streams. A lexical analyzer looks at the
patterns as they flow by and performs actions based on them. The lex
tool takes the parser and generates C code based on that, which is then
compiled. These patterns are based on regular expressions, which makes
them powerful and easy to construct. The actions are based largely on
C, with some macros and functions from the lex and yacc libraries.
[slide 7]
Here we see an example of some of the lex code in the main scanner in
czech. Some of the actions match some obvious things, like tabs,
newlines, and single characters, or words. The function "unput()" is
a lex function which places what you tell it to back on the stream.
REJECT is a macro that unputs what you matched. Once you have started
your action, you can continue to access the stream via the input()
function.
This piece of code is pretty ugly, by the way. I really need to clean it up to make it more readable and do some proper grammar checking. Niels Provos, a friend of mine, read it and said, "It makes my brain hurt."
[slide 8]
Like I mentioned above, you run this parser through the lex generator
to generate C code. Then you can compile it:
$ lex -t file.l > file.c $ cc -c file.c $ cc -o file file.o -ll -lyThat runs the parser "file.l" through lex to generate some C code, which you then compile. In the final linking step you link in the lex and yacc libraries for specific functions from them. Pretty simple. The flex manpage is a great tutorial on lex, by the way.
[page 9]
The project strategy was pretty simple, then, in the abstract, and would
focus the efforts on a lex parser. A yacc parser is for later (more
below).
To choice between a full C parser and a keyword tag was actually a decision between a complex design and a simple design. I chose the simpler one, but I will eventually have to move closer towards a C parser. Czech understands the improper usage of dangerous functions, like the printf() family for format string problems and the use of strcat() in loops, which should never be done.
[page 10]
The design philosophy of czech was pretty important for me. The main points
are:
[page 11]
The challenges facing any of these tools are very elemental. First you have
false positives, and then you have false negatives. Each will lead to
a decreased confidence in your tool, and discourage developers. You should
be able to understand new functions, such as glib or BIND, making it useful
for really large projects like GNOME. Lastly, remember than C is a very
flexible language, and no one codes similarily. Your tools should be able to
deal with this reality.
[page 12]
Czech as it stands is an initial attempt to implement these ideas. It uses
preprocessing in a first pass to expand macros and grab function prototypes,
as well as variable declarations. Basic type qualifying is performed,
as it builds two lists of data types. Data that is input from the user is
going to be treated far more strictly than data that is stically defined.
This is in the case of a string format issue, for example. Consider the
improper handling of a string below:
static char *stuff = "this is a string"; /* things happen */ syslog (LOG_INFO, stuff);Syslog has to worry about string formatting, but if you've defined a string yourself, you know what kind of data you have there, so you shouldn't throw a red flag on that (probably just a orange flag). Now, if you used a function like that and *stuff had user supplied content, then you should definitely check its formatting and its bounds. Czech attempts to do this for you with this split data types.
[page 13]
Czech is the first available component of project pedantic, which is designed
to be a set of source code analysis tools. Its written in about 1000 lines
of code, and runs realy fast (see performance, below) and is pretty easy
to use. Currently its not fully functional. While it can build the lists,
they're not yet used. This is more a matter of time and motivation right
now, but it should be pretty easy (using the OpenBSD QUEUE(3) interface).
Lastly, there are several really show stopper bugs in it right now.
However, its actually ready to drop into place of your C compiler in many Makefiles. Also, I've used it to actually find some bugs and have reported them to the right people.
[page 14]
Czechs key features are sumarized here:
I should note that these numbers are on my laptop, a P3/600 OpenBSD system. Filesystems, memory, and CPU will, of course, vary these numbers.
[page 16]
Here's an example of czech in action. In this trimmed example, czech
was used in the Makefile as a replacement for CC:
$ make CC=czech
czech -O2 -c www6to4.c
initializing czech 0130-04082002 in /home/jose/software/www6to4-1.5
scanning www6to4.c ...
line 120: possible buffer overflow in strcpy
line 487: possible buffer overflow in strcpy
line 505: possible buffer overflow in strcpy
total number of lines: 683
total number of matches: 3
And it finds a few keywords it warns you about. In the next slide
we analyze part of the output.
[page 17]
Here's a brief analysis of one of the strcpy() calls czech warned you
about:
481 while (fgets (buf, sizeof (buf), configfp)) {
482 char cmd[BUFSIZ], arg[BUFSIZ], tmp[BUFSIZ];
483 char *p, *q;
484
485 line_num++;
486
487 strcpy (tmp, buf);
In line 481 buf is a usersupplied vaariable, bounds checked by fgets().
In line 487 its called in strcpy() from buf to tmp. The risk here depends
on the relative sizes of the buffers, tmp and buf. One of the things
czech has to learn is how to calculate those values ...
In this case it is not an off by one error, as fgets() will accept sizeof(buf) - 1 characters. Both buf and tmp are defined as BUFSIZE in length, but the strcpy on line 487 will copy exactly BUFSIZE from buf to tmp with a NULL terminator.
[page 18]
So now let's talk about the limitations of czech. Like all lexical analysis
tools for static analysis, it doesn't really get to learn program flow. It
only looks top down in any one file, and has only the most basic understandings
of input and output.
Czech cannot examine all of the possible states of the code, instead it takes a basic case analysis. Perhaps it should take a worst case analysis. Like I said above, czech doesn't calculate the size of a variable's allocated buffer (but it should be easy to do so), or the return sizes of functions. And of course it has some serious bugs in it which prevent me from rolling up a 0.1 release (but you can check it out in CVS).
[page 19]
I would like to finish czech, but I will have to move to yacc grammar to do
so, I think. This will certainly make the lex code easier to understand.
I will also have to construct a rudamentary C parser, and of course examine
the sizes of the arguments to the functions for comparison. Lclint does this
for example, with a basic prototype of:
strcpy(dest, src); /* insist (size(src) =< sizeof(dest)) */
The second generation tool is in the design phase. Its named 'prauge', a play on the capital of the Czech republic, as well as the shorted "prog". I'm shooting for a dynamic analysis tool, possibly using the ptrace(2) functions to monitor arguments and how they are called, or perhaps the Gdb analysis engine (suggested by a couple of friends). I may be able to simply do static analysis from the output of the ktrace facility.
[page 20]
To conclude, while it certainly has some limitations, source code analysis
using lexical analysis techniques is worthwhile for development. However,
it can only assist the developer, not replace a manual audit. Lastly, such
tools are limited in the scope of their known grammar. Czech, an
implementation of such a tool, was quick to code for me, and is pretty easy
to use for most people, and runs very very fast on lots of code. However,
its has a way to go before it can return really useful data in a majority of
the situations.
Thank you, and I want to thank sarnold, viZard, MJesus, Fernand0, and Oroz, as well as all of the other people involved in Uninet Infosec. It's an honor to present here with such esteemed fellow presenters. Thank you!
Análisis léxico en la exploración del código de fuenteNota: éste es un borrador del qué será presentado en Uninet Infosec 2002 el sábado, 20 de abril, 2002. Una traducción de babelfish al español y francés aparece abajo. Las diapositivas están disponibles en mi sitioweb en: http://www.monkey.org/~jose/presentations/czech-rubicon02.d /
INTRODUCCIÓN
[ diapositiva 1 ]
Esta charla está diseña para introducir la aplicación de análisis léxico al análisis del código de fuente. Específicamente, el diseño y la implentación de la herramienta estática de análisis para el lenguaje de programación C, nombrada "czech", serán presentados. Varios defectos inherentes en análisis estático, el uso del análisis léxico en revisiones de código fuente, y las lecciones específicas aprendidas del incidente en el implentation del checo serán discutidos.[ diapositiva 2 ]
Rápidamente, daré una descripción de parte de la investigación actual con la que soy familiar en este area. Varias personas están procurando plasmar muchos, muchos años de métodos de evaluación de código fuente y herramientas para automatizar el análisis de seguridad de su código. Ésta es un área de alto interés tanto para investigadores corporativos como académicos. Yo introduciré cuales son las herramientas léxicas de generación de código y como funcionan, especificamente el uso de la herramienta "flexión", un analizador de sintaxis libremente disponible del "parser" lex. Luego mostraré las estrategias típicas para estas herramientas, y después ahondaré en los desafíos específicos hechos frente en la ejecución de la herramienta czech, para la herramienta y el autor así como para los usuarios de la herramienta.[ diapositiva 3 ]
Rápidamente, una descripción de "czech". Discutiré la filosofía de diseño de czech, y como hice el diseño y la implementación. El rendimiento de "czech" es algo de lo que soy absolutamente orgulloso. Daré algún ejemplo de como funciona y mostraré la salida en bruto de la herramienta, también discutiré algunos de los fallos de funcionamiento excepcionales actualmente. Finalmente, discutiré algunas de las directrices futuras para czech y el conjunto del proyecto pedantic.[ diapositiva 4 ]
A pesar de todo el interés que despierta actualmente, el análisis de código fuente no es nada nuevo. Los investigadores de ingeniería del software han estado haciendo esto durante años. En el campo de la seguridad, esto se ha convertido en un área caliente para los investigadores en años recientes, y muchos grupos grandes se han involucrado. Éstos incluyen David Wagner, David Evans, y Microsoft.Los dos acercamientos principales son el análisis estático, mirando código de fuente típicamente. El análisis dinámico, en contraste, toma el conjunto o partes del programa y lo ejecuta con diversas entradas, vigilando el comportamiento del programa. El análisis estático se centra en cosas como el análisis lógico del diseño, el análisis de flujo como maneja datos, y el análisis de los "qualifiers" del tipo en argumentos. Todos éstos tienen sus distintos puntos fuertes, incluyendo la posibilidad de ampliación, la facilidad de empleo, o la completitud de la cobertura.
Debe ser notado que ningún método da cobertura total, y cada uno carece de algunos aspectos. También, hay el problema de parada de Turing , donde sólo se puede examinar una pequeña fracción de todos los estados posibles del código en cualquier marco de tiempo dado. Como tal, hay que centrarse en algunos aspectos y hacer relaciones de compromiso entre la completitud y la eficacia.
[ diapositiva 5 ]
El proyecto pedantic debe ciertamente mucho a algunas de las herramientas estáticas más accesibles del análisis. Pscan era una de las primeras herramientas del análisis de formato de cadena, y se podía utilizar para encontrar algunos problemas comunes de los formatos cadena (véase también la charla de KF, más adelante). ITS4, y RATS posteriormente, eran también algunas de las herramientas comúnmente citadas para los errores de programación habituales. Ambos también se basan en análisis léxico, también. Flawfinder, basado en python, trabaja de forma parecida a RATS, pero toma algunas decisiones más elegantes. Finalmente, dos grandes herramientas a observar son Lclint y splint, ambas fruto de la investigación de David Evans y compañeros de trabajo en Virginia (los E.E.U.U.).Czech está muy inspirado en estas herramientas. De hecho, comencé a escribirlo después de que un artículo que escribí para el Linux Journal sobre RATS, ITS4 y Flawfinder y sentirme algo molesto con ellas. También, durante el diseño del czech, hablé con David Wheeler, el autor de Flawfinder. Intenté aprovechar mucho de este ' arte anterior '. Como nota de humor diré que el conjunto de pruebas para czech rompe RATS y Flawfinder.
[ diapositiva 6 ]
Lex es una herramienta para analizar flujos de entradas. Un analizador léxico mira los modelos según fluyen y realiza las acciones basadas en ellas. La herramienta lex toma el analizador de sintaxis y genera el código C basado en él, que entonces es compilado. Estos modelos se basan en expresiones regulares, lo que da mucho potencia y facilidad de construcción. Las acciones se basan en gran parte en C, con algunas macros y funciones de las bibliotecas lex y yacc.[ diapositiva 7 ]
Aquí vemos un ejemplo de algo de código lex en el explorador principal en czech. Algunas de las acciones corresponden con algunas cosas obvias, como tabulaciones, newlines, y caracteres, o palabras. La función " unput() " es una función de lex que coloca lo que se le dice hacia atrás en la secuencia. REJECT es una macro que "unputs" (quita) aquello que coincide. Una vez que se ha comenzado la acción, se puede continuar teniendo acceso a la secuencia vía la función del input().Este pedazo del código es bastante feo, a propósito. Realmente necesito limpiarlo hasta lo hago más legible y hacer algún chequeo de la gramática. Niels Provos, amigo mío, lo leyó y dijo, " hace que me duela el cerebro. "
[ diapositiva 8 ]
Como mencioné arriba, usted ejecuta este analizador de sintaxis a través de lex para generar código de C. Entonces usted puede compilarlo: $ lex - t file.l > file.c $ cc - c file.c $ cc - fichero file.o de o - ll - ly Eso ejecuta el analizador de sintaxis " file.l " a través de lex para generar un cierto código de C, que usted entonces compila. En el paso final de enlace se enlaza con las bibliotecas de lex y de yacc para las funciones específicas de ellas. Muy simple. La página man de flex es una gran gúia de lex, por cierto. [ paginación 9 ] La estrategia del proyecto era bastante simple, después, en el extracto, y se centraría los esfuerzos en un analizador de sintaxis del lex. Un analizador de sintaxis del yacc está para más adelante (más abajo). A la opción entre un analizador de sintaxis completo de C y la palabra clave una etiqueta era realmente una decisión entre un diseño complejo y un diseño simple. Elegí el más simple, pero tendré que eventual moverme más cerca hacia un analizador de sintaxis de C. El checo entiende el uso incorrecto de funciones peligrosas, como la familia del printf() para los problemas de la cadena del formato y el uso del strcat() en los bucles, que deben nunca ser hechos. [ paginación 10 ] La filosofía de diseño del checo era bastante importante para mí. Las puntas principales son: - el dont pide a mucho del revelador su desperdiciador de tiempo, el error propenso, y una salida grande un ejemplo es Lclint, una herramienta powwerful que requiera las anotaciones del código para el uso verdadero. Cqual es otro ejemplo, que requiere a reveladores modificar su código en una estructura de la lógica. En lugar, tiraba para una gota en el reemplazo para el centímetro cúbico en su makefile. - haga la salida fácil leer no los dé demasiado más a la preocupación alrededor - hágala extensible si usted amplía un API, usted debe poder entrenar a la herramienta bastante fácilmente. (fallé aquí desgraciadamente) - trabajo bastante rápidamente aunque usted tendrá que pasar mucho más el tiempo que mira concluído la salida, usted si la vuelta inmóvil en una cantidad de tiempo razonable - tentativa de entender flujo de programa el checo lo divide en flujos de datos (de entrada y de salida) del ingreso y de la salida [ paginación 11 ] Los desafíos que hacen frente a cualesquiera de estas herramientas son muy elementales. Primero usted tiene positivos falsos, y entonces usted tiene negativas falsas. Cada uno conducirá a una confianza disminuida en su herramienta, y desalienta los reveladores. Usted debe poder entender nuevas funciones, tales como fácil o ATA, haciéndolo útil para los prokects realmente grandes como GNOME. Pasado, recuerde que C es un lenguaje muy flexible, y nadie códigos similarily. Sus herramientas deben poder ocuparse de esta realidad. [ paginación 12 ] El checo como está parado es una tentativa inicial de poner estas ideas en ejecución. Utiliza el proceso previo en un primer paso para ampliar macros y para asir prototipos de la función, así como declaraciones variables. El tipo básico que califica se realiza, pues construye dos listas de los tipos de los datos. Los datos que se entran del utilizador van a ser tratados lejos más terminantemente que los datos que stically se definen. Esto está en el caso de una edición del formato de la cadena, por ejemplo. Considere la dirección incorrecta de una cadena abajo: carbón estático * la materia = " esto es una cadena "; / * las cosas suceden * / syslog (LOG_INFO, materia); El syslog tiene que preocuparse del formato de la cadena, pero si usted ha definido una cadena usted mismo, usted sabe qué clase de datos usted tiene allí, así que usted no debe lanzar un indicador rojo en eso (probablemente apenas un indicador anaranjado). Ahora, si usted utilizó una función como ese y * rellene tenía contenido provisto utilizador, después usted debe controlar definitivamente su formato y sus límites. Las tentativas checas de hacer esto para usted con esto partieron tipos de los datos. [ paginación 13 ] El checo es el primer componente disponible del proyecto pedantic, que se diseña para ser un conjunto de herramientas del análisis del código de fuente. Sus escritos en cerca de 1000 líneas de código, y los funcionamientos realy ayunan (véase el funcionamiento, abajo) y son bastante fáciles de utilizar. Actualmente su no completamente funcional. Mientras que puede construir las listas, todavía no se utilizan. Éste es más una cuestión de tiempo y de motivación ahora, pero debe ser bastante fácil (con el interfaz de OpenBSD QUEUE(3)). Pasado, hay varios realmente los fallos de funcionamiento del tapón de la demostración en él ahora. Sin embargo, su realmente listo caer en lugar de su compilador de C en muchos makefiles. También, lo he utilizado para encontrar algunos fallos de funcionamiento y para haber señaladolos realmente a la gente adecuada. [ paginación 14 ] Los checos que son las características dominantes sumarized aquí: - sabe un dígito binario sobre uso seguro un strcpy() con una cadena constante de la fuente es más seguro que una cadena de la longitud variable, pero aún no seguro. Y - puede no hacer caso con seguridad del uso del va_args() en la familia del printf(). - sabe un dígito binario sobre uso inseguro el más grande es el uso del strcat() en un bucle, que puede ser muy peligroso rápidamente. - trabaja tokenizing cada línea del código entonces evalúa la función y después toma las decisiones basadas en ésa. [ paginación 15 ] El funcionamiento del checo es bastante asombroso, dado la naturaleza enredada del código. En modo del solo paso (como checo - C * c) puede hacer cerca de 1 millón de líneas por minuto. Cuando usted hace análisis completo usando el proceso previo, usted ve sobre una pérdida 10x en funcionamiento. Debo observar que estos números están en mi computadora portátil, un sistema de P3/600 OpenBSD. Filesystems, la memoria, y la voluntad de la CPU, por supuesto, varían éstos número *** TRANSLATION ENDS HERE ***s. [page 16] Here's an example of czech in action. In this trimmed example, czech was used in the Makefile as a replacement for CC: $ make CC=czech czech -O2 -c www6to4.c initializing czech 0130-04082002 in /home/jose/software/www6to4-1.5 scanning www6to4.c ... line 120: possible buffer overflow in strcpy line 487: possible buffer overflow in strcpy line 505: possible buffer overflow in strcpy total number of lines: 683 total number of matches: 3 And it finds a few keywords it warns you about. In the next slide we analyze part of the output. [page 17] Here's a brief analysis of one of the strcpy() calls czech warned you about: 481 while (fgets (buf, sizeof (buf), configfp)) { 482 char cmd[BUFSIZ], arg[BUFSIZ], tmp[BUFSIZ]; 483 char *p, *q; 484 485 line_num++; 486 487 strcpy (tmp, buf); In line 481 buf is a usersupplied vaariable, bounds checked by fgets(). In line 487 its called in strcpy() from buf to tmp. The risk here depends on the relative sizes of the buffers, tmp and buf. One of the things czech has to learn is how to calculate those values ... [page 18] So now let's talk about the limitations of czech. Like all lexical analysis tools for static analysis, it doesn't really get to learn program flow. It only looks top down in any one file, and has only the most basic understandings of input and output. Czech cannot examine all of the possible states of the code, instead it takes a basic case analysis. Perhaps it should take a worst case analysis. Like I said above, czech doesn't calculate the size of a variable's allocated buffer (but it should be easy to do so), or the return sizes of functions. And of course it has some serious bugs in it which prevent me from rolling up a 0.1 release (but you can check it out in CVS). [page 19] I would like to finish czech, but I will have to move to yacc grammar to do so, I think. This will certainly make the lex code easier to understand. I will also have to construct a rudamentary C parser, and of course examine the sizes of the arguments to the functions for comparison. Lclint does this for example, with a basic prototype of: strcpy(dest, src); /* insist (size(src) = The second generation tool is in the design phase. Its named 'prauge', a play on the capital of the Czech republic, as well as the shorted "prog". I'm shooting for a dynamic analysis tool, possibly using the ptrace(2) functions to monitor arguments and how they are called, or perhaps the Gdb analysis engine (suggested by a couple of friends). I may be able to simply do static analysis from the output of the ktrace facility. [page 20] To conclude, while it certainly has some limitations, source code analysis using lexical analysis techniques is worthwhile for development. However, it can only assist the developer, not replace a manual audit. Lastly, such tools are limited in the scope of their known grammar. Czech, an implementation of such a tool, was quick to code for me, and is pretty easy to use for most people, and runs very very fast on lots of code. However, its has a way to go before it can return really useful data in a majority of the situations. Thank you, and I want to thank sarnold, viZard, MJesus, Fernand0, and Oroz, as well as all of the other people involved in Uninet. It's an honor to present here with such esteemed fellow presenters. Thank you!
Analyse lexicologique dans le balayage de code source
Note: c'est un writeout approximatif ce qui sera présenté chez Uninet Infosec Infosec 2002 samedi, de 20 avril, 2002. Une traduction de babelfish
en espagnol et le Français apparaît ci-dessous. Les glissières sont disponibles sur mon website à:
http://www.monkey.org/~jose/presentations/czech-rubicon02.d /
INTRODUCTION
[ diapositive 1 ]
Cet entretien est conçu pour présenter l'application de l'analyse lexicologique à l'analyse de code source. Specically, la conception et
l'implentation de l'outil statique d'analyse pour le langage de programmation de C, appelé "Tchèque", seront présentés. Plusieurs pailles
inhérentes dans l'analyse statique, l'utilisation de l'analyse lexicologique dans des revues de code source, et des leçons spécifiques
apprises de l'échec dans l'implentation du Tchèque seront discutées.
[ diapositive 2 ]
Brièvement, je donnerai une vue d'ensemble d'une partie de la recherche courante que je suis familier avec dans cette arène. Plusieurs
personnes essayent à la puissance plusieurs, beaucoup d'années des méthodes d'évaluation de code source et outils pour automatiser
l'analyse des valeurs de leur code. C'est un secteur d'intérêt élevé pour les chercheurs de corporation et scolaires de même. Moi
présenteront ce que sont les outils lexicologiques de génération de code et comment ils fonctionnent, specically l'utilisation de l'outil
d'"câble", un analyseur librement disponible de lex. Je décrirai alors des stratégies typiques pour ces outils, et fouille alors dans les défis
spécifiques relevés dans l'exécution de l'outil tchèque, pour l'outil et l'auteur aussi bien que pour des utilisateurs de l'outil.
[ diapositive 3 ]
Rapidement, une vue d'ensemble de la présentation spécifiquement au sujet du Tchèque. Je discuterai la philosophie de conception du
Tchèque, et puis comment j'ai conçu et ai puis exécuté l'exécution. L'exécution du Tchèque est quelque chose que je suis tout à fait fier de,
assez interestingly. Je donnerai un certain exemple de la façon dont il actionne et vous montre le rendement approximatif de l'outil, et
discute certains des bogues exceptionnels comme il se tient actuellement. Pour finir, je discuterai certaines des futures directions pour
tchèque et la totalité du projet pedantic.
[ diapositive 4 ]
En dépit de tout l'intérêt son obtenir de nos jours, analyse de code source n'est pas quelque chose nouveau. Les chercheurs de technologie
de la programmation avaient fait ceci pendant des années. Dans le royaume de sécurité, ceci est devenu un secteur chaud pour des
chercheurs ces dernières années, et beaucoup de grands groupes ont chimed dedans. Ceux-ci incluent David Wagner, David Evans, et
Microsoft.
Les deux grandes approches sont analyse statique, regardant le code source typiquement. L'analyse dynamique, dans le constract, prend la
totalité ou les parats du programme et les court avec l'entrée variable, surveillant le comportement du programme. L'analyse statique se
concentre sur des choses comme l'analyse logique de la conception, l'analyse de flux pendant qu'elle manipule des données, et l'analyse des
qualificateurs de type dans les arguments. Toute la ces derniers a leurs forces variables, y compris l'extendability, la facilité d'utilisation, ou
la perfection de l'assurance.
Il devrait certainement noter qu'aucune méthode ne donne l'assurance totale, et chacune manque quelques aspects. En outre, il y a le Turing
'problème stoppant ', où vous pouvez seulement examiner une petite fraction des états possibles du code dans n'importe quelle tranche de
temps donnée. En tant que tels, vous devez vous concentrer dedans sur quelques aspects et faire des différences entre la perfection et
l'efficacité.
[ diapositive 5 ]
Le projet pedantic doit certainement beaucoup à certains des outils statiques plus accessibles d'analyse. Pscan était un des premiers outils
d'analyse de corde de format, et pourrait être employé pour trouver quelques problèmes communs de corde de format (voir également
l'aujourd'hui postérieur de l'entretien de KF pour ce qui ces moyen). ITS4, et RATS postérieurs, étaient également certains des outils le plus
généralement cités pour des erreurs de programmation communes. Tous les deux sont également basés sur l'analyse lexicologique, aussi.
Flawfinder, basé sur le python, fonctionne similarily aux RATS, mais prend quelques décisions plus futées. Pour finir, deux grands outils à
noter sont Lclint et attelle, de la recherche de David Evans et collègues en Virginie (Etats-Unis).
Le Tchèque prend beaucoup d'inspiration de ces outils. En fait, j'ai commencé à l'écrire après qu'un morceau que j'ai écrit pour le journal de
Linux sur des RATS, ITS4 et Flawfinder et obtenir plutôt dérangé avec eux. En outre, pendant la conception du Tchèque, j'ai parlé au
cycliste de David, l'auteur de Flawfinder. J'ai essayé à la puissance beaucoup de cet 'art antérieur '. Je devrais également noter, dans
l'intéret de l'humeur, que la suite d'essai pour le Tchèque casse des RATS et Flawfinder.
[ diapositive 6 ]
Lex est un outil pour analyser des jets d'entrée. Un analyseur lexicologique regarde les modèles pendant qu'ils coulent près et effectue des
actions basées sur elles. L'outil de lex prend l'analyseur et produit du code de C basé sur cela, qui est alors compilé. Ces modèles sont
basés sur des expressions régulières, qui les rend puissantes et faciles à construire. Les actions sont basées en grande partie sur C, avec
quelques macros et fonctions des bibliothèques de lex et de yacc.
[ diapositive 7 ]
Ici nous voyons un exemple d'une partie du code de lex dans le module de balayage principal dans le Tchèque. Certaines des actions
assortissent quelques choses évidentes, comme des étiquettes, caractères NL, et caractères simples, ou mots. La fonction "unput()" est
une fonction de lex qui place ce que vous le dites de soutenir sur le jet. Le REJET est un macro ce des unputs ce que vous avez assorti.
Une fois que vous avez commencé votre action, vous pouvez continuer à accéder au jet par l'intermédiaire de la fonction d'input().
Ce morceau de code est assez laid, d'ailleurs. Je dois vraiment le nettoyer jusqu'à le rends plus lisible et fais la vérification appropriée de
grammaire. Niels Provos, un ami à moi, lu lui et dit, "il fait mon mal de cerveau."
[ diapositive 8 ]
Comme je mentionnais ci-dessus, vous courez cet analyseur par le générateur de lex pour produire du code de C. Alors vous pouvez le
compiler: $ de lex - t file.l > file.c $ cc - c file.c $ cc - dossier file.o de o - ll - ly qui court l'analyseur "file.l" par le lex pour produire d'un
certain code de C, que vous compilez alors. Dans l'étape d'enchaînement finale vous liez dans les bibliothèques de lex et de yacc pour des
fonctions spécifiques d'elles. Joli simple. Le page-manuel de câble est un grand cours d'instruction sur le lex, d'ailleurs.
[ page 9 ]
La stratégie de projet était assez simple, puis, dans l'abstrait, et concentrerait les efforts sur un analyseur de lex. Un analyseur de yacc est
pour plus tard (plus ci-dessous).
Au choix entre un plein analyseur de C et le mot-clé une étiquette était réellement une décision entre une conception complexe et une
conception simple. J'ai choisi le plus simple, mais je devrai par la suite me déplacer plus étroitement vers un analyseur de C. Le Tchèque
comprend l'utilisation inexacte des fonctions dangereuses, comme la famille de printf() pour des problèmes de corde de format et l'usage du
strcat() dans les boucles, qui devraient ne jamais être faites.
[ page 10 ]
La philosophie de conception du Tchèque était assez importante pour moi. Les points principaux sont:
- ne demandez pas à une grande partie du réalisateur
son long, l'erreur encline, et une grande sortie un exemple est Lclint, un outil powwerful qui exige des annotations du code pour le
vrai usage. Cqual est un autre exemple, qui exige des lotisseurs de remanier leur code dans une structure de logique. Au lieu de
cela, je tirais pour une baisse en remplacement pour le cc dans votre fichier makefile.
- rendez le rendement facile à lire
ne les donnez pas trop plus au souci environ
- rendez-l'extensible
si vous prolongez un api, vous devriez pouvoir former l'outil assez facilement. (j'ai échoué ici malheureux)
- travail assez rapidement
quoique vous deviez passer beaucoup plus le temps regardant au-dessus du rendement, vous si le retour immobile dans une
quantité de temps raisonnable
- tentative de comprendre l'écoulement de programme
le Tchèque le divise en flux de données (d'arrivée et outbound) d'entrée et de sortie
[ page 11 ]
Les défis faisant face à n'importe lequel de ces outils sont très élémentaires. D'abord vous avez les positifs faux, et alors vous avez les
négatifs faux. Chacun mènera à une confiance diminuée dans votre outil, et décourage des réalisateurs. Vous devriez pouvoir comprendre
de nouvelles fonctions, telles que facile ou LIEZ, le rendant utile pour les prokects vraiment grands comme GNOME. Pour finir,
rappelez-vous que C est une langue très flexible, et unique codes similarily. Vos outils devraient pouvoir traiter cette réalité.
[ page 12 ]
Le Tchèque sans modification est une première tentative de mettre en application ces idées. Elle emploie le prétraitement dans une
première passe pour augmenter des macros et pour saisir des prototypes de fonction, aussi bien que des déclarations variables. La
qualification de base de type est exécutée, car elle établit deux listes de types de données. Des données qui sont entrées de l'utilisateur
vont être traitées bien plus strictement que les données qui sont stically définies. C'est dans le cas d'une issue de format de corde, par
exemple. Considérez la manipulation inexacte d'une corde ci-dessous: char statique * la substance = "ceci est une corde"; les choses se
produisent */sgf (LOG_INFO, substance); Le sgf doit s'inquiéter du formatage de corde, mais si vous avez défini une corde vous-même,
vous savez quel genre de données vous avez là, ainsi vous ne devriez pas jeter un drapeau rouge sur cela (probablement juste un drapeau
orange). Maintenant, si vous employiez une fonction comme le ce et * bourrez a eu le contenu fourni par utilisateur, puis vous devriez
certainement vérifier son formatage et ses limites. Les tentatives tchèques de faire ceci pour vous avec ceci ont dédoublé des types de
données.
[ page 13 ]
Le Tchèque est le premier composant disponible du projet pedantic, qui est conçu pour être un ensemble d'outils d'analyse de code source.
Les ses écrits dans environ 1000 lignes de code, et les courses realy jeûnent (voir l'exécution, ci-dessous) et sont assez faciles à
employer. Actuellement son pas entièrement fonctionnel. Tandis qu'elle peut établir les listes, elles ne sont pas encore employées. C'est
plus une question de temps et de motivation en ce moment, mais il devrait être assez facile (en utilisant l'interface d'OpenBSD
QUEUE(3)). Pour finir, il y a plusieurs vraiment des bogues de taquet d'exposition dans lui en ce moment.
Cependant, son réellement prêt à se laisser tomber dans l'endroit de votre compilateur de C dans beaucoup de fichiers makefile. En outre, je
l'ai employé pour trouver quelques bogues et pour les avoir rapportés réellement aux personnes concernées.
[ page 14 ]
Les Tchèques les dispositifs que principaux sont sumarized ici:
- elle connaît un peu au sujet d'utilisation sûre
un strcpy() avec de la corde constante de source est plus sûr qu'une corde de longueur variable, mais toujours non sûr. Et il peut
sans risque ignorer l'utilisation du va_args() dans la famille de printf().
- il connaît un peu au sujet d'utilisation peu sûre
le plus grand est l'utilisation du strcat() dans une boucle, qui peut être très dangereuse rapidement.
- cela fonctionne à côté de tokenizing chaque ligne de code
il évalue alors la fonction et prend alors des décisions basées sur celle.
[ page 15 ]
L'exécution du Tchèque est assez étonnante, donné la nature empêtrée du code. En mode de passage simple (comme Tchèque - C * c) elle
peut faire environ 1 million de lignes par minute. Quand vous faites l'analyse complète en utilisant le prétraitement, vous voyez au sujet
d'une perte 10x dans l'exécution.
Je devrais noter que ces nombres sont sur mon laptop, un système de P3/600 OpenBSD. Filesystems, mémoire, et volonté d'unité centrale
de traitement, naturellement, changent ces derniers nombre *** TRANSLATION ENDS HERE ***s.
[page 16]
Here's an example of czech in action. In this trimmed example, czech was used in the Makefile as a replacement for CC:
$ make CC=czech
czech -O2 -c www6to4.c
initializing czech 0130-04082002 in /home/jose/software/www6to4-1.5
scanning www6to4.c ...
line 120: possible buffer overflow in strcpy
line 487: possible buffer overflow in strcpy
line 505: possible buffer overflow in strcpy
total number of lines: 683
total number of matches: 3
And it finds a few keywords it warns you about. In the next slide we analyze part of the output.
[page 17]
Here's a brief analysis of one of the strcpy() calls czech warned you about:
481 while (fgets (buf, sizeof (buf), configfp)) {
482 char cmd[BUFSIZ], arg[BUFSIZ], tmp[BUFSIZ];
483 char *p, *q;
484
485 line_num++;
486
487 strcpy (tmp, buf);
In line 481 buf is a usersupplied vaariable, bounds checked by fgets(). In line 487 its called in strcpy() from buf to tmp. The risk here
depends on the relative sizes of the buffers, tmp and buf. One of the things czech has to learn is how to calculate those values ...
[page 18]
So now let's talk about the limitations of czech. Like all lexical analysis tools for static analysis, it doesn't really get to learn program flow.
It only looks top down in any one file, and has only the most basic understandings of input and output.
Czech cannot examine all of the possible states of the code, instead it takes a basic case analysis. Perhaps it should take a worst case
analysis. Like I said above, czech doesn't calculate the size of a variable's allocated buffer (but it should be easy to do so), or the return
sizes of functions. And of course it has some serious bugs in it which prevent me from rolling up a 0.1 release (but you can check it out in
CVS).
[page 19]
I would like to finish czech, but I will have to move to yacc grammar to do so, I think. This will certainly make the lex code easier to
understand. I will also have to construct a rudamentary C parser, and of course examine the sizes of the arguments to the functions for
comparison. Lclint does this for example, with a basic prototype of:
strcpy(dest, src);
/* insist (size(src) =
The second generation tool is in the design phase. Its named 'prauge', a play
on the capital of the Czech republic, as well as the shorted "prog". I'm
shooting for a dynamic analysis tool, possibly using the ptrace(2)
functions to monitor arguments and how they are called, or perhaps the Gdb
analysis engine (suggested by a couple of friends). I may be able to
simply do static analysis from the output of the ktrace facility.
[page 20]
To conclude, while it certainly has some limitations, source code analysis
using lexical analysis techniques is worthwhile for development. However,
it can only assist the developer, not replace a manual audit. Lastly, such
tools are limited in the scope of their known grammar. Czech, an
implementation of such a tool, was quick to code for me, and is pretty easy
to use for most people, and runs very very fast on lots of code. However,
its has a way to go before it can return really useful data in a majority of
the situations.
Thank you, and I want to thank sarnold, viZard, MJesus, Fernand0, and Oroz, as well
as all of the other people involved in Uninet Infosec. It's an honor to present
here with such esteemed fellow presenters. Thank you!