Skip to content

Instantly share code, notes, and snippets.

@cfra

cfra/ISIS_TLV_ADDITION.md

Created February 8, 2019 12:58
Show Gist options
  • Save cfra/d4d72c13babf188464b12f7d73390c13 to your computer and use it in GitHub Desktop.
Save cfra/d4d72c13babf188464b12f7d73390c13 to your computer and use it in GitHub Desktop.
Download ZIP
Describes how to add new IS-IS TLV to FRR's isisd
Raw
ISIS_TLV_ADDITION.md

Adding a new TLV and SubTLVs to FRR's isisd

Protocol description

For this first example, we are going to add a TLV called hundred with the currently unassigned codepoint 100.

That TLV has the following assumed format:

  • one octet: type this is 100
  • one octet: length this is the length of the following value
  • four octets: payload an IP address which we consider a payload
  • one octet: subtlv len the length of SubTLVs which are following for the given IP, this might be zero
  • subtlv len octets: subtlvs SubTLVs for the given IP, might be omitted if subtlv_len is zero

Optionally, the TLV might me continued with more payload, subtlv len, subtlv blocks.

Implementation

First, we add a new datatype to store the information of the TLV. As there might be multiple instances of payload, we should ensure that the head of the new datatype matches struct isis_item, as we will be using the isis_item structure to store all the elements.

Also, we create a new context for parsing TLVs:

diff --git a/isisd/isis_tlvs.h b/isisd/isis_tlvs.h
index fce30d4ee..aaaceb3e2 100644
--- a/isisd/isis_tlvs.h
+++ b/isisd/isis_tlvs.h
@@ -196,6 +196,14 @@ struct isis_purge_originator {
        uint8_t sender[6];
 };
 
+struct isis_hundred;
+struct isis_hundred {
+       struct isis_hundred *next;
+
+       struct in_addr payload;
+       struct isis_subtlvs *subtlvs;
+};
+
 enum isis_auth_result {
        ISIS_AUTH_OK = 0,
        ISIS_AUTH_TYPE_FAILURE,
@@ -258,6 +266,7 @@ enum isis_tlv_context {
        ISIS_CONTEXT_SUBTLV_NE_REACH,
        ISIS_CONTEXT_SUBTLV_IP_REACH,
        ISIS_CONTEXT_SUBTLV_IPV6_REACH,
+       ISIS_CONTEXT_SUBTLV_HUNDRED,
        ISIS_CONTEXT_MAX
 };
 
@@ -280,6 +289,8 @@ enum isis_tlv_type {
        ISIS_TLV_PURGE_ORIGINATOR = 13,
        ISIS_TLV_EXTENDED_REACH = 22,
 
+       ISIS_TLV_HUNDRED = 100,
+
        ISIS_TLV_OLDSTYLE_IP_REACH = 128,
        ISIS_TLV_PROTOCOLS_SUPPORTED = 129,
        ISIS_TLV_OLDSTYLE_IP_REACH_EXT = 130,

Next, we extend the TLV handling code so that it handles the new TLV:

diff --git a/isisd/isis_tlvs.c b/isisd/isis_tlvs.c
index 5a6c7bc30..43087c859 100644
--- a/isisd/isis_tlvs.c
+++ b/isisd/isis_tlvs.c
@@ -96,7 +96,9 @@ static struct pack_order_entry pack_order[] = {
 	PACK_ENTRY(EXTENDED_IP_REACH, ISIS_ITEMS, extended_ip_reach),
 	PACK_ENTRY(MT_IP_REACH, ISIS_MT_ITEMS, mt_ip_reach),
 	PACK_ENTRY(IPV6_REACH, ISIS_ITEMS, ipv6_reach),
-	PACK_ENTRY(MT_IPV6_REACH, ISIS_MT_ITEMS, mt_ipv6_reach)};
+	PACK_ENTRY(MT_IPV6_REACH, ISIS_MT_ITEMS, mt_ipv6_reach),
+	PACK_ENTRY(HUNDRED, ISIS_ITEMS, hundreds),
+};
 
 /* This is a forward definition. The table is actually initialized
  * in at the bottom. */
@@ -2507,6 +2509,7 @@ struct isis_tlvs *isis_alloc_tlvs(void)
 	RB_INIT(isis_mt_item_list, &result->mt_ip_reach);
 	init_item_list(&result->ipv6_reach);
 	RB_INIT(isis_mt_item_list, &result->mt_ipv6_reach);
+	init_item_list(&result->hundreds);
 
 	return result;
 }
@@ -2579,6 +2582,9 @@ struct isis_tlvs *isis_copy_tlvs(struct isis_tlvs *tlvs)
 
 	rv->spine_leaf = copy_tlv_spine_leaf(tlvs->spine_leaf);
 
+	copy_items(ISIS_CONTEXT_LSP, ISIS_TLV_HUNDRED,
+	            &tlvs->hundreds, &rv->hundreds);
+
 	return rv;
 }
 
@@ -2646,6 +2652,9 @@ static void format_tlvs(struct isis_tlvs *tlvs, struct sbuf *buf, int indent)
 	format_tlv_threeway_adj(tlvs->threeway_adj, buf, indent);
 
 	format_tlv_spine_leaf(tlvs->spine_leaf, buf, indent);
+
+	format_items(ISIS_CONTEXT_LSP, ISIS_TLV_HUNDRED, &tlvs->hundreds,
+		     buf, indent);
 }
 
 const char *isis_format_tlvs(struct isis_tlvs *tlvs)
@@ -2699,6 +2708,7 @@ void isis_free_tlvs(struct isis_tlvs *tlvs)
 		      &tlvs->mt_ipv6_reach);
 	free_tlv_threeway_adj(tlvs->threeway_adj);
 	free_tlv_spine_leaf(tlvs->spine_leaf);
+	free_items(ISIS_CONTEXT_LSP, ISIS_TLV_HUNDRED, &tlvs->hundreds);
 
 	XFREE(MTYPE_ISIS_TLV, tlvs);
 }
@@ -3102,6 +3112,7 @@ ITEM_TLV_OPS(mt_router_info, "TLV 229 MT Router Information");
 TLV_OPS(threeway_adj, "TLV 240 P2P Three-Way Adjacency");
 ITEM_TLV_OPS(ipv6_address, "TLV 232 IPv6 Interface Address");
 ITEM_TLV_OPS(ipv6_reach, "TLV 236 IPv6 Reachability");
+ITEM_TLV_OPS(hundred, "TLV 100 Hundred");
 
 ITEM_SUBTLV_OPS(prefix_sid, "Sub-TLV 3 SR Prefix-SID");
 SUBTLV_OPS(ipv6_source_prefix, "Sub-TLV 22 IPv6 Source Prefix");
@@ -3116,6 +3127,7 @@ static const struct tlv_ops *tlv_table[ISIS_CONTEXT_MAX][ISIS_TLV_MAX] = {
 		[ISIS_TLV_PURGE_ORIGINATOR] = &tlv_purge_originator_ops,
 		[ISIS_TLV_EXTENDED_REACH] = &tlv_extended_reach_ops,
 		[ISIS_TLV_MT_REACH] = &tlv_extended_reach_ops,
+		[ISIS_TLV_HUNDRED] = &tlv_hundred_ops,
 		[ISIS_TLV_OLDSTYLE_IP_REACH] = &tlv_oldstyle_ip_reach_ops,
 		[ISIS_TLV_PROTOCOLS_SUPPORTED] = &tlv_protocols_supported_ops,
 		[ISIS_TLV_OLDSTYLE_IP_REACH_EXT] = &tlv_oldstyle_ip_reach_ops,
diff --git a/isisd/isis_tlvs.h b/isisd/isis_tlvs.h
index aaaceb3e2..fda27d877 100644
--- a/isisd/isis_tlvs.h
+++ b/isisd/isis_tlvs.h
@@ -242,6 +242,7 @@ struct isis_tlvs {
 	struct isis_mt_item_list mt_ipv6_reach;
 	struct isis_threeway_adj *threeway_adj;
 	struct isis_spine_leaf *spine_leaf;
+	struct isis_item_list hundreds;
 };
 
 #define ISIS_PREFIX_SID_READVERTISED  0x80

Because we registered the new TLV in all locations, but did not implement any of its actual packing/unpacking/copy or formatting functions, we get errors if we try to compile this. So, let's add these missing functions which do the actual work:

diff --git a/isisd/isis_tlvs.c b/isisd/isis_tlvs.c
index 43087c859..88f963fb1 100644
--- a/isisd/isis_tlvs.c
+++ b/isisd/isis_tlvs.c
@@ -817,6 +817,144 @@ out:
 
 	return 1;
 }
+/* Functions for TLV 100 - Hundred */
+
+/*
+ * Used when we copy one `struct isis_tlvs` to another.
+ *
+ * `i`: The item which should be copied.
+ *
+ * Returns a copy of the item
+ */
+static struct isis_item *copy_item_hundred(struct isis_item *i)
+{
+	struct isis_hundred *h = (struct isis_hundred *)i;
+	struct isis_hundred *rv = XCALLOC(MTYPE_ISIS_TLV, sizeof(*rv));
+
+	rv->payload = h->payload;
+	rv->subtlvs = copy_subtlvs(h->subtlvs);
+
+	return (struct isis_item*)rv;
+}
+
+/*
+ * Used to pretty-print items from TLVs.
+ *
+ * `mtid`:   Toplogy ID. Should be shown in the output in case of a
+ *           multi-topology TLV.
+ * `i`:      The item which should be formatted.
+ * `sbuf`:   The buffer where the format output should be written to.
+ * `indent`: The amound of whitespace to add before each line of log.
+ */
+static void format_item_hundred(uint16_t mtid, struct isis_item *i,
+				   struct sbuf *buf, int indent)
+{
+	struct isis_hundred *h = (struct isis_hundred *)i;
+	char ip_str[INET_ADDRSTRLEN];
+
+	inet_ntop(AF_INET, &h->payload, ip_str, sizeof(ip_str));
+
+	sbuf_push(buf, indent, "TLV Hundred:\n");
+	sbuf_push(buf, indent, "  Payload:%s\n", ip_str);
+
+	if (h->subtlvs) {
+		sbuf_push(buf, indent, "  Subtlvs:\n");
+		format_subtlvs(h->subtlvs, buf, indent + 4);
+	}
+}
+
+static void free_item_hundred(struct isis_item *i)
+{
+	struct isis_hundred *h = (struct isis_hundred *)i;
+
+	isis_free_subtlvs(h->subtlvs);
+	XFREE(MTYPE_ISIS_TLV, h);
+}
+
+/*
+ * Puts a single item on the wire. A TLV may contain multiple items.
+ *
+ * `i`:   The item we should pack
+ * `s`:   The stream we should pack to
+ *
+ * Returns 0 and pushes the item into the stream if successful.
+ * Returns 1 on error.
+ */
+static int pack_item_hundred(struct isis_item *i, struct stream *s)
+{
+	struct isis_hundred *h = (struct isis_hundred *)i;
+
+	if (STREAM_WRITEABLE(s) < 5)
+		return 1;
+
+	stream_put(s, &h->payload, 4);
+
+	if (h->subtlvs) {
+		pack_subtlvs(h->subtlvs, s);
+	} else {
+		stream_putc(s, 0);
+	}
+
+	return 0;
+}
+
+/*
+ * Decodes an item from the wire. A TLV may contain one or multiple items.
+ *
+ * `mtid`:   Topology ID.
+ *           If the item is an MTID item, `mtid` should be used to put it into
+ *           the right list, otherwise (like here) it can be ignored.
+ * `len`:    Number of octets available inside of the TLV we are decoding
+ * `s`:      Stream we are reading the item from
+ * `log`:    Log where we are writing the unpack log to
+ * `dest`:   Pointer to the `struct isis_tlvs` which we should unpack to
+ * `indent`: The number of spaces by which the log should be indented
+ *
+ * Returns 0 and appends unpacked item to dest->hundreds on successful read,
+ * otherwise 1.
+ */
+static int unpack_item_hundred(uint16_t mtid, uint8_t len, struct stream *s,
+				  struct sbuf *log, void *dest, int indent)
+{
+	struct isis_tlvs *tlvs = dest;
+	struct isis_hundred *rv = NULL;
+
+	sbuf_push(log, indent, "Unpacking TLV hundred...\n");
+	if (len < 5) {
+		sbuf_push(log, indent,
+			  "Not enough data left. (expected 5 or more bytes, got %"
+			  PRIu8 ")\n", len);
+		goto out;
+	}
+
+	rv = XCALLOC(MTYPE_ISIS_TLV, sizeof(*rv));
+	stream_get(&rv->payload, s, 4);
+
+	uint8_t subtlv_len = stream_getc(s);
+
+	if (len < 5 + subtlv_len) {
+		sbuf_push(log, indent,
+			  "Expected %" PRIu8
+			  " bytes of subtlvs, but only %u bytes available.\n",
+			  subtlv_len, len - 5);
+		goto out;
+	}
+
+	rv->subtlvs = isis_alloc_subtlvs(ISIS_CONTEXT_SUBTLV_HUNDRED);
+	if (unpack_tlvs(ISIS_CONTEXT_SUBTLV_HUNDRED, subtlv_len, s,
+	                log, rv->subtlvs, indent + 4)) {
+		goto out;
+	}
+
+	format_item_hundred(mtid, (struct isis_item *)rv, log, indent + 2);
+	append_item(&tlvs->hundreds, (struct isis_item *)rv);
+	return 0;
+
+out:
+	if (rv)
+		free_item_hundred((struct isis_item*)rv);
+	return 1;
+}
 
 /* Functions related to TLV 128 (Old-Style) IP Reach */
 static struct isis_item *copy_item_oldstyle_ip_reach(struct isis_item *i)

This completes the actual implementation of the TLV from the perser perspective. To send out the TLV, a function similar to the exiting isis_tlvs_add_ functions should be added to isis_tlvs.c and isis_tlvs.h respectively.

It can then be used from lsp_build to add this TLV to the originated information.

Subtlvs should be added to the newly created context in a similar way as this TLV was just added to ISIS_CONTEXT_LSP. The matching functions should be implemented similarly to the functions for the TLV that were just implemented. See the _subtlv_ipv6_source_prefix functions for example.

Testing

If we now run make check it will probably fail in TestFuzzIsisTLV.test_exit_cleanly. The reason for this is that there are precreated fuzztests for the IS-IS parser. Since we added a new TLV Type just now, the parser's output differs from the expected output:

$ ./tests/isisd/test_fuzz_isis_tlv | grep differs
Test 118 failed, output differs.
Test 135 failed, output differs.
Test 175 failed, output differs.
Test 228 failed, output differs.
Test 264 failed, output differs.
Test 267 failed, output differs.
Test 291 failed, output differs.
Test 314 failed, output differs.
Test 388 failed, output differs.

We should verify that each of the diffs is actually valid:

$ ./tests/isisd/test_fuzz_isis_tlv 2>/dev/null | grep differs | awk '{ print $2; }' | \
        while read -r test; do ./tests/isisd/test_fuzz_isis_tlv $test | less; done

This will show all the failing testcases. They are probably failing because we now try to unpack TLV 100 which is present in these testcases instead of skipping it as unknown TLV.

Once we have verified these diffs, we can be relatively certain that we did not break the behavior for previously existing TLVs.

We should however ensure that our newly created TLV parsers are also robust and create new test-cases to cover them.

For that purpose, we are using AFL. In addition to AFL we are using a wrapper called wuschl which uses the information from AFL to create a set of testcases which can then be executed without AFL installed.

To update the test-cases, you should install AFL and rebuild FRR with export CC=afl-gcc set. This will create the instrumentation to run the fuzxzing.

Afterwards, install wuschl using something like pip2 install wuschl, the exact command depends on your distribution.

Now, you dump out the existing testcases for use as starting point for AFL (make sure you have built the test programms too):

$ wuschl fill_input tests/isisd/test_fuzz_isis_tlv

After the old testcases have been written out for AFL, you can run the fuzzing against your newly written code. However, this currently does not work well with the libtool wrapper, so you need to move the real binary and ensure you have the necessary libraries installed.

$ sudo make install
$ cp ./tests/isisd/.libs/test_fuzz_isis_tlv tests/isisd/test_fuzz_isis_tlv
$ wuschl fuzz tests/isisd/test_fuzz_isis_tlv

AFL will probably complain about some of your system settings like CPU frequency scaling governor. Fix them and rerun the fuzzing command until AFL runs.

Let it run for a while, at least unti one or two cylces have been complete.

If you did well, you won't observe any crashes. Otherwise, now is the time to go back and fix them.

Once you are happy with the amount of fuzzing done, exit AFL with Ctrl + C.

The work done by AFL can be used to create a corpus of testcases with good branch coverage. This can be done by:

$ wuschl update tests/isisd/test_fuzz_isis_tlv

As the generated testdata is not really human readable anyway, it is store in the repository in compressed form. So replace the old version by the one just created by wuschl:

$ gzip -f tests/isisd/test_fuzz_isis_tlv_tests.h

That should be it. When you now run make check again, the fuzztest should pass again and your new TLVs should be covered.

Code

The code for this exercise can be found here

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment