[Feature] Provenance

[nandavelugoti]

• Problem/Issue at hand
• Provenance
• Implementation details
  • Steps involved in building Provenance information
  • Maintaining/Accessing Provenance information
  • Provenance usage in Nautilus Kernel
  • Provenance Shell Commands
  • Shell command usage:
  • Running Provenance shell commands
  • Monitor output after panic
• Testing
• ToDos, future scope and more

Table of contents generated with markdown-toc

Problem/Issue at hand

Currently, Nautilus only implements backtrace logic to output a list of call stack addresses. But it is really hard to infer/extract information from those addresses. Provenance is built to solve that problem.

Provenance

Provenance is a debugger framework for Nautilus. The idea here is to maintain debug information, of nautilus kernel, which can be used to extract appropriate information (symbol, section, line number, etc.) given an address at runtime.

Provenance, with this feature PR, will be able to map symbol and section information to a given address.

Implementation details

Provenance is implemented as an individual component within nautilus kernel which can be enabled/disabled using Kconfig.

Steps involved in building Provenance information

1. If Kconfig option is enabled for Provenance, then generate Symbol Table (nautilus.syms) and Section Table (nautilus.secs) information from nautilus.bin as part of build processes. Both the tables are sorted by addresses of entries in ascending order.
2. Add both these generated files as multiboot modules to Grub configuration along with the kernel.
3. In the kernel bootup process, read and parse those modules to build Provenance information if the Kconfig option is enabled for Provenance.

Maintaining/Accessing Provenance information

• Provenance defines a unified data structure, prov_table, to contain both Symbol Table and Section Table information.
• prov_table contains a list of another Provenance data structure, prov_entry, to maintain each Symbol/Section Table entry and the length of the list.
• Each prov_entry has a name, start address, end address, and size members.
• Both the lists of entries are sorted by their start address in ascending order.
• So whenever there is a query, provenance does a simple binary (interval) search on Symbol/Section tables to get the appropriate information.

Provenance usage in Nautilus Kernel

• Provenance information is currently utilized by two other nautilus components:
  • Backtrace
  • Monitor
• The usage details are illustrated in the Shell Commands section.

Provenance Shell Commands

The Provenance feature also implements a shell command with various arguments.

Shell command usage:

provenance [ panic | info addr | bt ]

Running Provenance shell commands

Monitor output after panic

Testing

• provtest is a test command registered with testing framework with following arguments:
  • bt: Output backtrace (default)
  • info addr: Get information (section/symbol) of a given address

ToDos, future scope and more

• At this point in time, Provenance only has Section and Symbol table information. But this can be extended to maintain more useful debug information such as file information, line number information, etc. DWARF debug information could be used to achieve the same
• Generating nice runtime provenance graphs (and present them à la radare2-like tools)
• Instruction-level/data provenance
• For more about Provenance, refer to this Google Doc.

[nandavelugoti]

Worker information
hostname: 2bf01d11-1ac9-404a-bb2e-d9280cf8b6aa@1.worker-com-5686bd95fc-nxrdr.gce-production-3
version: v6.2.17 https://github.com/travis-ci/worker/tree/bc420764f334fe0d096a417c80426f672f1b7d18
instance: travis-job-e7ea11fd-d047-4c35-bef6-faff4650de0b travis-ci-sardonyx-xenial-1593004276-4d46c6b3 (via amqp)
startup: 6.057581204s

$ travis_apt_get_update

git.checkout
$ git clone --depth=50 https://github.com/HExSA-Lab/nautilus.git HExSA-Lab/nautilus

Encrypted environment variables have been removed for security reasons.
See https://docs.travis-ci.com/user/pull-requests/#pull-requests-and-security-restrictions
$ export TRAVIS_COMPILER=gcc
$ export CC=${CC:-gcc}
$ export CC_FOR_BUILD=${CC_FOR_BUILD:-gcc}
$ gcc --version
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.12) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

1.45s$ pip install pyyaml --user
$ scripts/run_tests.py
Hello World
  HOSTCC  scripts/basic/fixdep
  HOSTCC  scripts/basic/split-include
  HOSTCC  scripts/basic/docproc
make[2]: Nothing to be done for '.config'.
  HOSTCC  scripts/kconfig/conf.o
  HOSTCC  scripts/kconfig/kxgettext.o
  HOSTCC  scripts/kconfig/mconf.o
  HOSTCC  scripts/kconfig/zconf.tab.o
  HOSTLD  scripts/kconfig/conf
scripts/kconfig/conf -s Kconfig
#
# using defaults found in .config
#
*
* Restart config...
*
*
* Debugging
*
Compile with Debug Symbols (DEBUG_INFO) [N/y/?] n
Enable Debugging Prints (DEBUG_PRINTS) [N/y/?] n
Enable Runtime Assertions (ENABLE_ASSERTS) [N/y/?] n
Enable Runtime Provenance Information (PROVENANCE) [N/y/?] (NEW)

No output has been received in the last 10m0s, this potentially indicates a stalled build or something wrong with the build itself.
Check the details on how to adjust your build configuration on: https://docs.travis-ci.com/user/common-build-problems/#build-times-out-because-no-output-was-received

The build has been terminated

The build is failing at Enable Runtime Provenance Information (PROVENANCE) [N/y/?] (NEW). My suspicion is: a change in Kconfig (that introduces a NEW configuration) is making make defconfig indefinitely waiting for the y/N input.