Code Structure
==============

A code structure test analyzes the structure of a translation unit's source code and enforces the predefined rules.
Each translation unit requires its own set of rules.
If the analyzed code violates at least one rule, the test is failed, and feedback on what rules have been violated is given.
Otherwise, feedback that the code structure test has been passed successfully is given.

There are three different types of rules:

1. *General rules:* These rules can be defined on every level.
2. *Global rules:* These rules can only be defined at a global level.
3. *Function rules:* These rules can only be defined at the function level.

.. note::

    If a rule is defined globally, each function is expected to abide by it, but rules on the function level supersede global definitions within their bodies.

In the following sections, the rules, their meaning, and default values are explained in detail.
The remainder of this section lists the different rules for each level.

**General rules:**

- :ref:`input`: allow/disallow/expect ``stdin`` input.
- :ref:`output`: allow/disallow/expect ``stdout`` output.
- :ref:`insecure`: allow/disallow/expect ``stderr`` output.
- :ref:`recursion`: allow/disallow/expect recursion.
- :ref:`disallowed_keywords`: List of disallowed keywords.
- :ref:`expected_keywords`: List of expected keywords.
- :ref:`allowed_function_calls`: List of allowed function calls.
- :ref:`disallowed_function_calls`: List of disallowed function calls.
- :ref:`expected_function_calls`: List of expected function calls.
- :ref:`expected_variable_declarations`: List of expected variable definitions.

**Rules exclusive to the global definition:**

- :ref:`required_functions`: List of function prototypes defining required functions.
- :ref:`disallowed_includes`: List of C-library names that are not allowed.
- :ref:`global_variables`: allow/disallow global variable declarations.
- :ref:`compile_args`: compiler arguments for clang AST-generation
- :ref:`functions`: Key that indicates the start of the list function rule segments.


**Additional rules for function level are:**

- :ref:`function`: function name

.. todo:
    - :ref:`compile_args`: What is this?


A key mechanic of code structure tests is that all keyword and function usages and whether recursive functions are used are propagated to the calling function.

General Rules
-------------

These rules can be used on both the global and function level.
If a rule is defined on the global level, functions must abide by it as well, but functions can supersede rules defined on the global level either partially or fully.
The following sections describe all general rules.

.. _input:

``input``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This rule indicates whether input from ``stdin`` is *allowed*, *disallowed* or *expected*.
This is achieved by allowing/disallowing or expecting the usage of at least one of the following functions:

.. raw:: html

    <details>
    <summary><a>Input Functions</a> (click to expand)</summary>

- ``fgetc``
- ``fgets``
- ``fgetwc``
- ``fread``
- ``fscanf``
- ``fscanf_s``
- ``fwscanf``
- ``fwscanf_s``
- ``getc``
- ``getc_unlocked``
- ``getchar``
- ``getchar_unlocked``
- ``getdelim``
- ``getline``
- ``gets``
- ``gets_s``
- ``getw``
- ``getwc``
- ``getwchar``
- ``getwline``
- ``pread``
- ``read``
- ``readv``
- ``scanf``
- ``scanf_s``
- ``sscanf``
- ``sscanf_s``
- ``swscanf``
- ``swscanf_s``
- ``vfscanf``
- ``vfscanf_s``
- ``vfwscanf``
- ``vfwscanf_s``
- ``vscanf``
- ``vscanf_s``
- ``vsscanf``
- ``vsscanf_s``
- ``vswscanf``
- ``vswscanf_s``
- ``vwscanf``
- ``vwscanf_s``
- ``wscanf``
- ``wscanf_s``

.. raw:: html

    </details>

If defined globally, this rule can be superseded on function level either partially, by defining :ref:`allowed_function_calls`, or :ref:`expected_function_calls`, or as a whole by redefining ``input``.

.. note::

    Please note that *expected* is not yet implemented! Currently, *expected* behaves just like *allowed*.

**Possible values:**

- ``true``: usage of at least one of the functions is expected (this is not implemented yet! currently ``true`` behaves just like ``null``)
- ``null``: usage of the functions is allowed but not mandatory.
- ``false``: usage of the functions is disallowed

Example:

.. code-block:: yaml

    input: false

**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If the keyword ``input`` is omitted on the global level, input is allowed.

.. _output:

``output``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This rule indicates whether output on ``stdout`` is *allowed*, *disallowed* or *expected*.
This is achieved by allowing/disallowing or expecting the usage of at least one of the following functions:

.. raw:: html

    <details>
    <summary><a>Output Functions</a> (click to expand)</summary>

- ``ferror``
- ``fprintf``
- ``fprintf_s``
- ``fpurge``
- ``fputc``
- ``fputs``
- ``fputwc``
- ``fputws``
- ``fputws_l``
- ``fread``
- ``freopen``
- ``fropen``
- ``fwprintf``
- ``fwrite``
- ``perror``
- ``printf``
- ``printf_s``
- ``putc``
- ``putchar``
- ``puts``
- ``putw``
- ``putwc``
- ``putwchar``
- ``pwrite``
- ``vasprintf``
- ``vfprintf``
- ``vfprintf_s``
- ``vfwprintf``
- ``vfwprintf_s``
- ``vprintf``
- ``vprintf_s``
- ``vwprintf``
- ``vwprintf_s``
- ``wprintf``
- ``write``
- ``writev``

.. raw:: html

    </details>

If defined globally, this rule can be superseded on function level either partially, by defining :ref:`allowed_function_calls` or :ref:`expected_function_calls`, or as a whole by redefining ``output``.

.. note::

    Please note that *expected* is not yet implemented! Currently, *expected* behaves just like *allowed*.

**Possible values:**

- ``true``: usage of at least one of the functions is expected (this is not implemented yet! currently ``true`` behaves just like ``null``)
- ``null``: usage of the functions is allowed but not mandatory.
- ``false``: usage of the functions is disallowed

Example:

.. code-block:: yaml

    output: null

**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If the keyword ``output`` is omitted on the global level output is allowed.

.. _insecure:

``insecure``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This rule indicates whether the usage of insecure functions is *allowed*, *disallowed* or *expected*.
Insecure functions are functions that start or kill processes or threads as well as the ``exec``-function family.
This is achieved by allowing/disallowing or expecting the usage of at least one of the following functions:

.. raw:: html

    <details>
    <summary><a>Insecure Functions</a> (click to expand)</summary>

- ``fork``
- ``system``
- ``kill``
- ``killpg``
- ``execl``
- ``execle``
- ``execlp``
- ``execv``
- ``execvp``
- ``execvP``
- ``execve``
- ``execvpe``
- ``fexecve``
- ``vfork``
- ``clone``
- ``tkill``
- ``tgkill``
- ``execveat``
- ``pthread_create``
- ``thrd_create``

.. raw:: html

    </details>


If defined globally, this rule can be superseded on function level either partially, by defining :ref:`allowed_function_calls` or :ref:`expected_function_calls`, or as a whole by redefining ``insecure``.

.. note::

    Please note that *expected* is not yet implemented! Currently, *expected* behaves just like *allowed*.

**Possible values:**

- ``true``: usage of at least one of the functions is expected (this is not implemented yet! currently ``true`` behaves just like ``null``)
- ``null``: usage of the functions is allowed but not mandatory.
- ``false``: usage of the functions is disallowed

Example:

.. code-block:: yaml

    insecure: false

**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If the keyword ``insecure`` is omitted on the global level, insecure functions are is allowed.

.. todo: change to default=false for security reasons?

.. _recursion:

``recursion``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This rule indicates whether recursion is *allowed*, *disallowed*, or *expected*.
If defined globally, this rule can be superseded on function level by redefining ``recursion``.

**Possible values:**

- ``true``: recursion is expected. If used globally, this means that every function has to be recursive. If used on the function level, the current function has to be recursive.
- ``null``: recursion is is allowed but not mandatory.
- ``false``: recursion is disallowed.

Example:

.. code-block:: yaml

    recursion: true

**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If the keyword ``recursion`` is omitted on the global level, recursion is allowed.

.. _disallowed_keywords:

``disallowed_keywords``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The usage of all keywords listed here is disallowed.
If defined globally, this rule can be superseded on the function level by adding globally disallowed keywords to :ref:`expected_keywords`.

**Possible values:**

A list of c-keywords that is not allowed

Example:

.. code-block:: yaml

    disallowed_keywords:
      - for
      - while
      - do


**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If ``disallowed_keywords`` is omitted on the global level, all keywords are allowed.


.. _expected_keywords:

``expected_keywords``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The usage of all keywords listed here is expected.
If defined globally, this rule can be superseded on the function level by adding globally expected keywords to :ref:`disallowed_keywords`.

**Possible values:**

A list of c-keywords that is expected

Example:

.. code-block:: yaml

    expected_keywords:
      - if
      - unsigned


**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If ``expected_keywords`` is omitted on the global level, all keywords are allowed.


.. _allowed_function_calls:

``allowed_function_calls``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The usage of all function calls of external functions listed here is allowed.
If defined globally, this rule can be superseded on the function level by adding globally allowed function calls to :ref:`disallowed_function_calls` or :ref:`expected_function_calls`.

**Possible values:**

A list of c-library function calls that is allowed.

Example:

.. code-block:: yaml

    allowed_function_calls:
      - printf
      - fprintf


**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If ``allowed_function_calls`` is omitted on the global level, all function calls are allowed.


.. _disallowed_function_calls:

``disallowed_function_calls``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The usage of all function calls of external functions listed here is disallowed.
If defined globally, this rule can be superseded on the function level by adding globally disallowed function calls to :ref:`allowed_function_calls` or :ref:`expected_function_calls`.

**Possible values:**

A list of C-library function calls that are not allowed.

.. code-block:: yaml

    disallowed_function_calls:
      - pow


**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If ``disallowed_function_calls`` is omitted on the global level, all function calls are allowed.


.. _expected_function_calls:

``expected_function_calls``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The usage of all function calls of external functions listed here is expected.
If defined globally, this rule can be superseded on the function level by adding globally expected function calls to :ref:`allowed_function_calls` or :ref:`disallowed_function_calls`.

**Possible values:**

A list of C-library function calls that are expected.

.. code-block:: yaml

    expected_function_calls:
      - qsort

**Default value:**

If it is not present on the function level, the global settings remain unchanged.
If ``expected_function_calls`` is omitted on the global level, all function calls are allowed.


.. _expected_variable_declarations:

``expected_variable_declarations``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The variables defined in this list are expected to be defined with the same type in the analyzed code.
If defined globally, this means that each function body must contain this variable definition.
If defined on function level, only the function body in question must contain the variable definitions.
This rule can not be superseded on the function level.

.. note::

    We plan on adding function parameters to the analyzed code for variable declarations. This is not yet implemented.

**Possible values:**

The list of variable declarations that are expected.

Example:

.. code-block:: yaml

    expected_variable_declarations:
      - 'long int n;'
      - 'long long value;'


**Default value:**

If ``expected_variable_declarations`` is omitted there are no expected variable declarations.


Global Rules
------------

These rules can only be used on the global level, and it is not possible to influence them on the function level.
The following sections describe all global rules.

.. _required_functions:

``required_functions``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The function prototypes defined in this list must be present in the analyzed code.

**Possible values:**

The list of c function prototypes that must be present

Example 1:

.. code-block:: yaml

    required_functions:
      - "void foo(int);"
      - "int bar(void);"

Example 2:

.. code-block:: yaml

    required_functions:
      - "#include \"types.h\" \n void print_person(person_t *person);"
      - "#include <stdlib.h> \nvoid my_sort(char array[], size_t length);"

.. note::
    As shown in Example 2, non standard types and types defined with typedef can be loaded via includes. **Attention:** The ``types.h`` file must reside in the same location as the test configuration fie and the ``Tests.py`` file.

Alternatively the same required functions can be written as:

.. code-block:: yaml

    required_functions:
      - |
          #include "types.h"
          void print_person(person_t *person);
      - |
          #include <stdlib.h>
          void my_sort(char array[], size_t length);"

**Default value:**

If ``required_functions`` is omitted, there are no functions whose implementation is required.

.. _disallowed_includes:

``disallowed_includes``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The usage of C-library includes listed here is not allowed in the analyzed code.

**Possible values:**

The list of c-library includes that are disallowed

Example:

.. code-block:: yaml

    disallowed_includes:
      - 'stdio.h'

**Default value:**

If ``disallowed_includes`` is omitted, all c-library includes are allowed.


.. _global_variables:

``global_variables``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Indicates whether global variables can be used in the analyzed translation unit or not.
If ``global_variables`` is true, the usage of global variables is allowed.
If ``global_variables`` is false, the usage of global variables is not allowed.


Example:

.. code-block:: yaml

    global_variables: false

**Default value:**

If ``global_variables`` is omitted, the usage of global variables is not allowed.

.. _compile_args:

``compile_args``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This keyword can be used to define an array containing additional command line arguments that should be passed to clang when it is parsing the syntax tree.
For example they can be used to specify include paths or warnings.

Example:

.. code-block:: yaml

    compile_args:
      - "-I/path/to/include"
      - "-Wall"

.. _functions:

``functions``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This key indicates the start of the function rules list.
It is required if rules for at least one function are defined. Otherwise, it is disallowed.


Function Rules
--------------

These rules can only be used on function level.
The following sections describe all function rules.

.. note::

    If function ``f1`` calls function ``f2`` then function ``f2`` must also abide to all rules for function ``f1`` because all checks are propagated backward along the call graph.

.. _function:

``function``
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

This key indicates the name of the function to which the following rules are applied. This key can only be used in the :ref:`functions` list.

**Possible values:**

The name of the function

Example:

.. code-block:: yaml

    functions:
      - function: print_something
        output: true
      - function: main
        output: true


**Default value:**

The ``function`` key can not be omitted if rules for a given function are to be added.


Example code structure test definitions:
----------------------------------------

In this section, a few examples for code structure test definitions are given.

.. note:: For security reasons, ``insecure: false`` is included in each of the following test cases. Omit ``insecure: false`` at your own risk.

**Example 1 (incorrect):** Output via printf is only allowed in function ``print_hello_world`` but ``print_hello_world`` is called in the function ``main``

.. code-block:: yaml
    :linenos:

    version: "0.0"
    translation_unit: hello_world.c
    tests:
      - type: structural
        name: Structural
        insecure: false
        output: false
        required_functions:
          - "void print_hello_world(void);"
        functions:
          - function: print_hello_world
            expected_function_calls:
              - printf
          - function: main
            expected_function_calls:
              - print_hello_world

Lets suppose the function ``print_hello_world`` calls the ``printf`` function. The ``printf``-call triggers an infringement of the global rule ``output: false`` because the printf call is propagated backward along the call-graph from ``print_hello_world`` to ``main``.

**Example 1 (correct):** Output is only allowed in functions ``print_hello_world`` and ``main``

.. code-block:: yaml
    :linenos:
    :emphasize-lines: 16

    version: "0.0"
    translation_unit: hello_world.c
    tests:
      - type: structural
        name: Structural
        insecure: false
        output: false
        required_functions:
          - "void print_hello_world(void);"
        functions:
          - function: print_hello_world
            expected_function_calls:
              - printf
          - function: main
            expected_function_calls:
              - print_hello_world
              - printf

Lets suppose the function ``print_hello_world`` calls the ``printf`` function. In this case the ``printf``-call does not trigger an infringement of the global rule ``output: false`` because the rule has been overridden for all functions along the call-graph, in this specific case ``print_hello_world`` and ``main``.