DNSTABLE-ENCODING(5)DNSTABLE-ENCODING(5)NAMEdnstable-encoding - key-value encoding format used by dnstable
DESCRIPTION
dnstable has been designed to import the data generated by the
nmsg-dns-cache program in the NMSG SIE/dnsdedupe format. See the ISC
Passive DNS Architecture whitepaper for details about how this data is
actually generated. The data model used with the aid of this format
preserves a number of important properties like Resource Record type
transparency and Resource Record set atomicity. Additionally, dnstable
preserves extra metadata available in the dnsdedupe payloads.
dnstable makes use of the MTBL Sorted String Table (SSTable) format,
which provides an immutable mapping of keys to values. This format
allows fast lookups of key prefixes, so the precise encoding and layout
of dnstable keys are chosen to take advantage of this property.
The utility dnstable_convert(1) included with the dnstable distribution
reads the following fields in the NMSG-encoded input dnsdedupe
payloads:
· rrname, the RRset owner name.
· rrclass, the RRset class, which is always Internet (IN) class, so
is omitted from actually being encoded.
· rrtype, the RRset type.
· rdata, an array of one or more record data values, in sorted order.
· bailiwick, the domain name of the closest enclosing zone of the
RRset.
· time_first, earliest timestamp that the RRset was observed.
· time_last, latest timestamp that the RRset was observed.
· count, the number of times the RRset was observed between
time_first and time_last.
Multiple key-value entries are generated for each RRset payload and
these key-value entries are stored in an MTBL-encoded data file. These
entries then allow for various types of useful passive DNS specific
lookups. MTBL keys and values are arbitrary byte arrays, and because
MTBL keys are stored in sorted order it is possible to look up entire
key-value entries by searching for the initial part of a key.
The first byte of each dnstable key is a “type” byte, and there are
currently four different “types” of dnstable key-value entries which
are described below. These different types are used to encode the full
passive DNS payload as well as “indices” into the payload.
Each dnstable key is a compound key that packs individual fields
together, and for the key types that include a value, the value is a
compound value that also packs individual fields together.
In the string literals given in the text below, C-style "\xNN" hex
encoding may be used to represent particular byte values. For example,
"\x03" is an octet with decimal value 3.
Key-value entry types
All keys and values described below are byte arrays containing packed
fields. Each field is concatenated together without delimiters. The
following data types are used:
· Byte.
· Fixed-width 16 bit integer.
· Variable-width integer.
· Wire-format DNS record data.
· Wire-format DNS domain names. The domain name "www.example.com"
would be encoded as "\x03www\x07example\x03com\x00".
· Label-reversed wire-format DNS domain names. The domain name
"www.example.com" would be encoded as
"\x03com\x07example\x03www\x00".
ENTRY_TYPE_RRSET
This entry type encodes the complete passive DNS payload. The RRset
owner name is encoded at the beginning of the key so that “forward”
lookups can be performed on the owner name. The owner name is also
encoded with labels reversed from the usual DNS order to increase
locality and allow for wildcard matches. (For example,
"*.example.com".)
The key is a packed tuple consisting of the following fields, in
order:
1. Type byte. The constant "\x00".
2. RRset owner name. Label-reversed wire-format DNS domain name.
3. RRset type. Variable-width integer.
4. Bailiwick domain name. Label-reversed wire-format DNS domain
name.
5. Rdata array. An array of one or more wire-format DNS record
data values. Each record data value is preceded by its length,
encoded as a variable-width integer.
The value consists of the following fields, in order:
1. First timestamp. Variable-width integer. Number of seconds
since the epoch.
2. Last timestamp. Variable-width integer. Number of seconds since
the epoch.
3. Count. Variable-width integer. Number of observations between
the first and last timestamps.
ENTRY_TYPE_RRSET_NAME_FWD
This entry type encodes only the RRset owner name in the usual
“forward” direction. This entry type provides an “index” into the
ENTRY_TYPE_RRSET “table” so that RRsets whose owner names start
with a particular subsequence of labels can be found. (For example,
looking up the label subsequence "www.example.*" using this index
would reveal the existence of the domain names "www.example.com",
"www.example.net", etc.)
The key consists of the following fields, in order:
1. Type byte. The constant "\x01".
2. RRset owner name. Wire-format DNS domain name.
There is no value associated with this entry type.
ENTRY_TYPE_RDATA
This entry type encodes individual Resource Record data values;
that is, an RRset containing multiple Resource Records will be
encoded as multiple entries in this “table”.
The key consists of the following fields, in order:
1. Type byte. The constant "\x02".
2. Rdata. Wire-format DNS record data.
3. RR type. Variable-width integer.
4. RR owner name. Label-reversed wire-format DNS domain name.
5. Rdata length. Fixed-width 16 bit integer. Number of bytes in
the Rdata field.
The Rdata length field is encoded at the end of the key so that
searches can be performed over the Rdata field without needing to
know the length of the record data value in advance (or worse,
needing to iterate over all possible length values).
ENTRY_TYPE_RDATA is also used to encode an entry sub-type
specifically for MX and SRV DNS records, which contain a DNS domain
name offset into the latter part of the record data. (An MX record
contains a domain name offset 2 octets into the record data value,
and a SRV record contains a domain name offset 6 octets into the
record data value. If the MX and SRV record data types had been
laid out with the domain name at the beginning of the record data
the following hack would not be necessary in order to make the
domain name part of these record types searchable.) This sub-type
“slices” the record data so that the domain name in the latter part
of the record appears at the beginning of the key and the initial
bytes of the record appear just before the Rdata length field at
the end of the key. That is, the key consists of the following
fields, in order:
1. Type byte. The constant "\x02".
2. Latter data slice. Wire-format DNS record data. This is the
latter part of the record data.
3. RR type. Variable-width integer.
4. RR owner name. Label-reversed wire-format DNS domain name.
5. Initial data slice. Wire-format DNS record data. This is the
initial part of the record data.
6. Latter data slice length. Fixed-width 16 bit integer. Number of
bytes in the latter data slice. The number of bytes in the
initial data slice is implicit.
The value consists of the following fields, in order:
1. First timestamp. Variable-width integer. Number of seconds
since the epoch.
2. Last timestamp. Variable-width integer. Number of seconds since
the epoch.
3. Count. Variable-width integer. Number of observations between
the first and last timestamps.
This is the same encoding as the values for ENTRY_TYPE_RRSET
entries.
ENTRY_TYPE_RDATA_NAME_REV
This entry type encodes label-reversed domain names from the record
data value for certain DNS record types that contain a domain name
in the record data, specifically the NS, CNAME, DNAME, PTR, MX, and
SRV DNS record types.
The key consists of the following fields, in order:
1. Type byte. The constant "\x03".
2. Rdata name. Label-reversed wire-format DNS domain name.
There is no value associated with this entry type.
EXAMPLES
This section gives two example RRsets and shows how they would be
encoded using the above entry types. The first example is an NS
delegation RRset for the domain name "example.com" and consists of two
Resource Records; it will result in the generation of six key-value
entries. The second example is an A-record for the domain name
"www.isc.org" that consists of a single Resource Record; it will result
in the generation of three key-value entries.
In each example entry, a table of the broken down fields in each entry
is given, and then the final, concatenated key and value byte strings.
Example 1: example.com./NS
Given the following passive DNS payload:
┌───────────┬─────────────────────────┐
│Field │ Value │
├───────────┼─────────────────────────┤
│ │ │
│rrname │ example.com. │
├───────────┼─────────────────────────┤
│ │ │
│rrtype │ NS │
├───────────┼─────────────────────────┤
│ │ │
│rdata │ ns1.example.com. │
├───────────┼─────────────────────────┤
│ │ │
│rdata │ ns2.example.com. │
├───────────┼─────────────────────────┤
│ │ │
│bailiwick │ com. │
├───────────┼─────────────────────────┤
│ │ │
│time_first │ Mon Apr 2 12:33:20 2012 │
├───────────┼─────────────────────────┤
│ │ │
│time_last │ Mon Apr 2 15:20:00 2012 │
├───────────┼─────────────────────────┤
│ │ │
│count │ 23 │
└───────────┴─────────────────────────┘
The following entries will be generated:
example.com entry #1 (ENTRY_TYPE_RRSET)
┌───────────┬─────────────────────────────────┬─────────────────────┐
│Field │ Data │ Interpretation │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│type │ "\x00" │ ENTRY_TYPE_RRSET │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rrname │ "\x03com\x07example\x00" │ example.com. │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rrtype │ "\x02" │ NS │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│bailiwick │ "\x03com\x00" │ com. │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata │ "\x11" │ ns1.example.com. │
│ │ "\x03ns1\x07example\x03com\x00" │ │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata │ "\x11" │ ns2.example.com. │
│ │ "\x03ns2\x07example\x03com\x00" │ │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│time_first │ "\x90\xb9\xe6\xfb\x04" │ 1333370000 (Mon Apr │
│ │ │ 2 12:33:20 2012) │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│time_last │ "\xa0\x87\xe7\xfb\x04" │ 1333380000 (Mon Apr │
│ │ │ 2 15:20:00 2012) │
├───────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│count │ "\x17" │ 23 │
└───────────┴─────────────────────────────────┴─────────────────────┘
Final key:
"\x00\x03com\x07example\x00\x02\x03com\x00\x11\x03ns1\x07example\x03com\x00\x11\x03ns2\x07example\x03com\x00"
Final value:
"\x90\xb9\xe6\xfb\x04\xa0\x87\xe7\xfb\x04\x17"
example.com entry #2 (ENTRY_TYPE_RRSET_NAME_FWD)
┌───────┬──────────────────────────┬───────────────────────────┐
│Field │ Data │ Interpretation │
├───────┼──────────────────────────┼───────────────────────────┤
│ │ │ │
│type │ "\x01" │ ENTRY_TYPE_RRSET_NAME_FWD │
├───────┼──────────────────────────┼───────────────────────────┤
│ │ │ │
│rrname │ "\x07example\x03com\x00" │ example.com. │
└───────┴──────────────────────────┴───────────────────────────┘
Final key:
"\x01\x07example\x03com\x00"
example.com entry #3 (ENTRY_TYPE_RDATA)
┌─────────────┬─────────────────────────────────┬─────────────────────┐
│Field │ Data │ Interpretation │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│type │ "\x02" │ ENTRY_TYPE_RDATA │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata │ "\x03ns1\x07example\x03com\x00" │ ns1.example.com. │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rrtype │ "\x02" │ NS │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rrname │ "\x03com\x07example\x00" │ example.com. │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata length │ "\x00\x11" │ rdata field is 17 │
│ │ │ octets long │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│time_first │ "\x90\xb9\xe6\xfb\x04" │ 1333370000 (Mon Apr │
│ │ │ 2 12:33:20 2012) │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│time_last │ "\xa0\x87\xe7\xfb\x04" │ 1333380000 (Mon Apr │
│ │ │ 2 15:20:00 2012) │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│count │ "\x17" │ 23 │
└─────────────┴─────────────────────────────────┴─────────────────────┘
Final key:
"\x02\x03ns1\x07example\x03com\x00\x02\x03com\x07example\x00\x00\x11"
Final value:
"\x90\xb9\xe6\xfb\x04\xa0\x87\xe7\xfb\x04\x17"
example.com entry #4 (ENTRY_TYPE_RDATA)
┌─────────────┬─────────────────────────────────┬─────────────────────┐
│Field │ Data │ Interpretation │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│type │ "\x02" │ ENTRY_TYPE_RDATA │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata │ "\x03ns2\x07example\x03com\x00" │ ns2.example.com. │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rrtype │ "\x02" │ NS │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rrname │ "\x03com\x07example\x00" │ example.com. │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata length │ "\x00\x11" │ rdata field is 17 │
│ │ │ octets long │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│time_first │ "\x90\xb9\xe6\xfb\x04" │ 1333370000 (Mon Apr │
│ │ │ 2 12:33:20 2012) │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│time_last │ "\xa0\x87\xe7\xfb\x04" │ 1333380000 (Mon Apr │
│ │ │ 2 15:20:00 2012) │
├─────────────┼─────────────────────────────────┼─────────────────────┤
│ │ │ │
│count │ "\x17" │ 23 │
└─────────────┴─────────────────────────────────┴─────────────────────┘
Final key:
"\x02\x03ns2\x07example\x03com\x00\x02\x03com\x07example\x00\x00\x11"
Final value:
"\x90\xb9\xe6\xfb\x04\xa0\x87\xe7\xfb\x04\x17"
example.com entry #5 (ENTRY_TYPE_RDATA_NAME_REV)
┌───────────┬─────────────────────────────────┬───────────────────────────┐
│Field │ Data │ Interpretation │
├───────────┼─────────────────────────────────┼───────────────────────────┤
│ │ │ │
│type │ "\x03" │ ENTRY_TYPE_RDATA_NAME_REV │
├───────────┼─────────────────────────────────┼───────────────────────────┤
│ │ │ │
│rdata name │ "\x03com\x07example\x03ns1\x00" │ ns1.example.com. │
└───────────┴─────────────────────────────────┴───────────────────────────┘
Final key:
"\x03\x03com\x07example\x03ns1\x00"
example.com entry #6 (ENTRY_TYPE_RDATA_NAME_REV)
┌───────────┬─────────────────────────────────┬───────────────────────────┐
│Field │ Data │ Interpretation │
├───────────┼─────────────────────────────────┼───────────────────────────┤
│ │ │ │
│type │ "\x03" │ ENTRY_TYPE_RDATA_NAME_REV │
├───────────┼─────────────────────────────────┼───────────────────────────┤
│ │ │ │
│rdata name │ "\x03com\x07example\x03ns2\x00" │ ns2.example.com. │
└───────────┴─────────────────────────────────┴───────────────────────────┘
Final key:
"\x03\x03com\x07example\x03ns2\x00"
Example 2: www.isc.org./A
Given the following passive DNS payload:
┌───────────┬─────────────────────────┐
│Field │ Value │
├───────────┼─────────────────────────┤
│ │ │
│rrname │ www.isc.org. │
├───────────┼─────────────────────────┤
│ │ │
│rrtype │ A │
├───────────┼─────────────────────────┤
│ │ │
│rdata │ 149.20.64.42 │
├───────────┼─────────────────────────┤
│ │ │
│bailiwick │ isc.org. │
├───────────┼─────────────────────────┤
│ │ │
│time_first │ Mon Apr 2 12:33:20 2012 │
├───────────┼─────────────────────────┤
│ │ │
│time_last │ Mon Apr 2 15:20:00 2012 │
├───────────┼─────────────────────────┤
│ │ │
│count │ 1 │
└───────────┴─────────────────────────┘
The following entries will be generated:
www.isc.org entry #1 (ENTRY_TYPE_RRSET)
┌───────────┬─────────────────────────┬─────────────────────┐
│Field │ Data │ Interpretation │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│type │ "\x00" │ ENTRY_TYPE_RRSET │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│rrname │ "\x03org\x03isc\x03www" │ www.isc.org. │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│rrtype │ "\x01" │ A │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│bailiwick │ "\x03org\x03isc\x00" │ isc.org. │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│rdata │ "\x04" │ 149.20.64.42 │
│ │ "\x95\x14\x40\x2a" │ │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│time_first │ "\x90\xb9\xe6\xfb\x04" │ 1333370000 (Mon Apr │
│ │ │ 2 12:33:20 2012) │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│time_last │ "\xa0\x87\xe7\xfb\x04" │ 1333380000 (Mon Apr │
│ │ │ 2 15:20:00 2012) │
├───────────┼─────────────────────────┼─────────────────────┤
│ │ │ │
│count │ "\x01" │ 1 │
└───────────┴─────────────────────────┴─────────────────────┘
Final key:
"\x00\x03org\x03isc\x03www\x01\x03org\x03isc\x00\x04\x95\x14\x40\x2a"
Final value:
"\x90\xb9\xe6\xfb\x04\xa0\x87\xe7\xfb\x04\x01"
www.isc.org entry #2 (ENTRY_TYPE_RRSET_NAME_FWD)
┌───────┬─────────────────────────────┬───────────────────────────┐
│Field │ Data │ Interpretation │
├───────┼─────────────────────────────┼───────────────────────────┤
│ │ │ │
│type │ "\x01" │ ENTRY_TYPE_RRSET_NAME_FWD │
├───────┼─────────────────────────────┼───────────────────────────┤
│ │ │ │
│rrname │ "\x03www\x03isc\x03org\x00" │ www.isc.org. │
└───────┴─────────────────────────────┴───────────────────────────┘
Final key:
"\x01\x03www\x03isc\x03org\x00"
www.isc.org entry #3 (ENTRY_TYPE_RDATA)
┌─────────────┬─────────────────────────────┬─────────────────────┐
│Field │ Data │ Interpretation │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│type │ "\x02" │ ENTRY_TYPE_RDATA │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata │ "\x95\x14\x40\x2a" │ 149.20.64.42 │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│rrtype │ "\x01" │ A │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│rrname │ "\x03org\x03isc\x03www\x00" │ www.isc.org. │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│rdata length │ "\x00\x04" │ rdata field is 4 │
│ │ │ octets long │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│time_first │ "\x90\xb9\xe6\xfb\x04" │ 1333370000 (Mon Apr │
│ │ │ 2 12:33:20 2012) │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│time_last │ "\xa0\x87\xe7\xfb\x04" │ 1333380000 (Mon Apr │
│ │ │ 2 15:20:00 2012) │
├─────────────┼─────────────────────────────┼─────────────────────┤
│ │ │ │
│count │ "\x01" │ 1 │
└─────────────┴─────────────────────────────┴─────────────────────┘
Final key:
"\x02\x95\x14\x40\x2a\x01\x03osc\x03isc\x03www\x00\x00\x04"
Final value:
"\x90\xb9\xe6\xfb\x04\xa0\x87\xe7\xfb\x04\x01"
SEE ALSO
ISC Passive DNS Architecture,
http://users.isc.org/~edmonds/passive-dns-architecture.pdf, for a
description of the process that generates the data that
dnstable_convert(1) reads as input.
Google Protocol Buffers Encoding,
https://developers.google.com/protocol-buffers/docs/encoding, for the
base-128 variable-width integer encoding used in some of the fields in
dnstable keys. Also see mtbl_varint(3) for a varint encoding
implementation.
11/10/2015 DNSTABLE-ENCODING(5)
