CVE-2021-43114: Other (NVD-CWE-Other)
value: FORT Validator versions prior to 1.5.2 will crash if an RPKI CA publishes an X.509 EE certificate. This will lead to RTR clients such as BGP routers to lose access to the RPKI VRP data set, effectively disabling Route Origin Validation.
CWE description: NVD is only using a subset of CWE for mapping instead of the entire CWE, and the weakness type is not covered by that subset.
CVSS v3 base score: 7.5
Published: 2021-11-09T13:15Z
Repository: https://github.com/NICMx/FORT-validator
Language: C
Files changed: src/rrdp/rrdp_objects.c, src/rrdp/rrdp_objects.h, src/rrdp/rrdp_parser.c, src/xml/relax_ng.c, test/Makefile.am, test/rrdp_objects_test.c
Commit date: 2021-09-04 00:05:17 -0500
Commit message: RRDP Notification: Optimize delta parse

It was allocating the deltas array twice, for seemingly no reason.
Also, the array slots were pointers, and the two arrays pointed to
different instances of the same objects. For seemingly no reason.

Now there's only one array, and it stores the objects directly.

Also adds relevant unit tests.

Diff: diff --git a/src/rrdp/rrdp_objects.c b/src/rrdp/rrdp_objects.c
index b8d1c05..a885bf2 100644
--- a/src/rrdp/rrdp_objects.c
+++ b/src/rrdp/rrdp_objects.c
@@ -3,30 +3,11 @@
 #include <errno.h>
 #include <stdlib.h>
 #include <string.h>
 #include "log.h"
 
-/*
- * List of deltas inside an update notification file.
- *
- * The structure functions are extended and will have the following meaning:
- *   - capacity : is the size of the array, must be set before using the array
- *                and can't be modified.
- *   - len      : number of elements set in the array.
- *
- * This struct is a diff version of array_list, utilized to store only the
- * amount of deltas that may be needed and validate that an update notification
- * file has a contiguous set of deltas.
- */
-struct deltas_head {
-	/** Unidimensional array. Initialized lazily. */
-	struct delta_head **array;
-	/** Number of elements in @array. */
-	size_t len;
-	/** Actual allocated slots in @array. */
-	size_t capacity;
-};
+DEFINE_ARRAY_LIST_FUNCTIONS(deltas_head, struct delta_head, )
 
 void
 global_data_init(struct global_data *data)
 {
 	data->session_id = NULL;
@@ -39,173 +20,22 @@ global_data_cleanup(struct global_data *data)
 }
 
 void
 doc_data_init(struct doc_data *data)
 {
+	data->uri = NULL;
 	data->hash = NULL;
 	data->hash_len = 0;
-	data->uri = NULL;
 }
 
 void
 doc_data_cleanup(struct doc_data *data)
 {
 	free(data->hash);
 	free(data->uri);
 }
 
-int
-delta_head_create(struct delta_head **result)
-{
-	struct delta_head *tmp;
-
-	tmp = malloc(sizeof(struct delta_head));
-	if (tmp == NULL)
-		return pr_enomem();
-
-	doc_data_init(&tmp->doc_data);
-
-	*result = tmp;
-	return 0;
-}
-
-void
-delta_head_destroy(struct delta_head *delta_head)
-{
-	if (delta_head) {
-		doc_data_cleanup(&delta_head->doc_data);
-		free(delta_head);
-	}
-}
-
-static void
-deltas_head_init(struct deltas_head *list)
-{
-	list->array = NULL;
-	list->len = 0;
-	list->capacity = 0;
-}
-
-static void
-deltas_head_cleanup(struct deltas_head *list)
-{
-	size_t i;
-
-	for (i = 0; i < list->capacity; i++)
-		delta_head_destroy(list->array[i]);
-	if (list->array)
-		free(list->array);
-}
-
-static int
-deltas_head_create(struct deltas_head **deltas)
-{
-	struct deltas_head *tmp;
-
-	tmp = malloc(sizeof(struct deltas_head));
-	if (tmp == NULL)
-		return pr_enomem();
-
-	deltas_head_init(tmp);
-
-	*deltas = tmp;
-	return 0;
-}
-
-static void
-deltas_head_destroy(struct deltas_head *deltas)
-{
-	deltas_head_cleanup(deltas);
-	free(deltas);
-}
-
-int
-deltas_head_set_size(struct deltas_head *deltas, size_t capacity)
-{
-	size_t i;
-
-	if (deltas->array != NULL)
-		pr_crit("Size of this list can't be modified");
-
-	deltas->capacity = capacity;
-	if (capacity == 0)
-		return 0; /* Ok, list can have 0 elements */
-
-	deltas->array = malloc(deltas->capacity
-	    * sizeof(struct delta_head *));
-	if (deltas->array == NULL)
-		return pr_enomem();
-
-	/* Point all elements to NULL */
-	for (i = 0; i < deltas->capacity; i++)
-		deltas->array[i] = NULL;
-
-	return 0;
-}
-
-/*
- * A new delta_head will be allocated at its corresponding position inside
- * @deltas (also its URI and HASH will be allocated). The position is calculated
- * using the difference between @max_serial and @serial.
- *
- * The following errors can be returned due to a wrong @position:
- *   -EEXIST: There's already an element at @position.
- *   -EINVAL: @position can't be inside @deltas list, meaning that such element
- *            isn't part of a contiguous list.
- *
- * Don't forget to call deltas_head_set_size() before this!!
- */
-int
-deltas_head_add(struct deltas_head *deltas, unsigned long max_serial,
-    unsigned long serial, char *uri, unsigned char *hash, size_t hash_len)
-{
-	struct delta_head *elem;
-	size_t position;
-	int error;
-
-	position = deltas->capacity - 1 - (max_serial - serial);
-	if (position < 0 || position > deltas->capacity - 1)
-		return -EINVAL;
-
-	if (deltas->array[position] != NULL)
-		return -EEXIST;
-
-	elem = NULL;
-	error = delta_head_create(&elem);
-	if (error)
-		return error;
-
-	elem->serial = serial;
-
-	elem->doc_data.uri = strdup(uri);
-	if (elem->doc_data.uri == NULL) {
-		free(elem);
-		return pr_enomem();
-	}
-
-	elem->doc_data.hash_len = hash_len;
-	elem->doc_data.hash = malloc(hash_len);
-	if (elem->doc_data.hash == NULL) {
-		free(elem->doc_data.uri);
-		free(elem);
-		return pr_enomem();
-	}
-	memcpy(elem->doc_data.hash, hash, hash_len);
-
-	deltas->array[position] = elem;
-	deltas->len++;
-
-	return 0;
-}
-
-/* Are all expected values set? */
-bool
-deltas_head_values_set(struct deltas_head *deltas)
-{
-	return deltas->len == deltas->capacity;
-}
-
 /* Do the @cb to the delta head elements from @from_serial to @max_serial */
 int
 deltas_head_for_each(struct deltas_head *deltas, unsigned long max_serial,
     unsigned long from_serial, delta_head_cb cb, void *arg)
 {
@@ -221,51 +51,103 @@ deltas_head_for_each(struct deltas_head *deltas, unsigned long max_serial,
 
 	pr_val_debug("Getting RRDP deltas from serial %lu to %lu.", from_serial,
 	    max_serial);
 	from = deltas->capacity - (max_serial - from_serial);
 	for (index = from; index < deltas->capacity; index++) {
-		error = cb(deltas->array[index], arg);
+		error = cb(&deltas->array[index], arg);
 		if (error)
 			return error;
 	}
 
 	return 0;
 }
 
+static int
+swap_until_sorted(struct delta_head *deltas, unsigned int i,
+    unsigned long min, unsigned long max)
+{
+	unsigned int target_slot;
+	struct delta_head tmp;
+
+	while (true) {
+		if (deltas[i].serial < min || max < deltas[i].serial) {
+			return pr_val_err("Deltas: Serial '%lu' is out of bounds. (min:%lu, max:%lu)",
+			    deltas[i].serial, min, max);
+		}
+
+		target_slot = deltas[i].serial - min;
+		if (i == target_slot)
+			return 0;
+		if (deltas[target_slot].serial == deltas[i].serial) {
+			return pr_val_err("Deltas: Serial '%lu' is not unique.",
+			    deltas[i].serial);
+		}
+
+		/* Simple swap */
+		tmp = deltas[target_slot];
+		deltas[target_slot] = deltas[i];
+		deltas[i] = tmp;
+	}
+}
+
 int
-update_notification_create(struct update_notification **file)
+deltas_head_sort(struct deltas_head *deltas, unsigned long max_serial)
 {
-	struct update_notification *tmp;
-	struct deltas_head *list;
+	unsigned long min_serial;
+	struct delta_head *cursor;
+	array_index i;
 	int error;
 
-	tmp = malloc(sizeof(struct update_notification));
-	if (tmp == NULL)
-		return pr_enomem();
+	if (max_serial + 1 < deltas->len)
+		return pr_val_err("Deltas: Too many deltas (%zu) for serial %lu. (Negative serials not implemented.)",
+		    deltas->len, max_serial);
 
-	list = NULL;
-	error = deltas_head_create(&list);
-	if (error) {
-		free(tmp);
-		return error;
-	}
-	tmp->deltas_list = list;
-	tmp->uri = NULL;
+	min_serial = max_serial + 1 - deltas->len;
 
-	global_data_init(&tmp->global_data);
-	doc_data_init(&tmp->snapshot);
+	ARRAYLIST_FOREACH(deltas, cursor, i) {
+		error = swap_until_sorted(deltas->array, i, min_serial,
+		    max_serial);
+		if (error)
+			return error;
+	}
 
-	*file = tmp;
 	return 0;
 }
 
+struct update_notification *
+update_notification_create(char const *uri)
+{
+	struct update_notification *result;
+
+	result = malloc(sizeof(struct update_notification));
+	if (result == NULL)
+		return NULL;
+
+	global_data_init(&result->global_data);
+	doc_data_init(&result->snapshot);
+	deltas_head_init(&result->deltas_list);
+	result->uri = strdup(uri);
+	if (result->uri == NULL) {
+		free(result);
+		return NULL;
+	}
+
+	return result;
+}
+
+static void
+delta_head_destroy(struct delta_head *delta)
+{
+	doc_data_cleanup(&delta->doc_data);
+}
+
 void
 update_notification_destroy(struct update_notification *file)
 {
 	doc_data_cleanup(&file->snapshot);
 	global_data_cleanup(&file->global_data);
-	deltas_head_destroy(file->deltas_list);
+	deltas_head_cleanup(&file->deltas_list, delta_head_destroy);
 	free(file->uri);
 	free(file);
 }
 
 int
diff --git a/src/rrdp/rrdp_objects.h b/src/rrdp/rrdp_objects.h
index a3048aa..b34970b 100644
--- a/src/rrdp/rrdp_objects.h
+++ b/src/rrdp/rrdp_objects.h
@@ -1,10 +1,11 @@
 #ifndef SRC_RRDP_RRDP_OBJECTS_H_
 #define SRC_RRDP_RRDP_OBJECTS_H_
 
 #include <stddef.h>
 #include <stdbool.h>
+#include "data_structure/array_list.h"
 
 /* Possible results for an RRDP URI comparison */
 typedef enum {
 	/* The URI exists and has the same session ID and serial */
 	RRDP_URI_EQUAL,
@@ -60,45 +61,43 @@ struct snapshot {
 	struct global_data global_data;
 };
 
 /* Delta element located at an update notification file */
 struct delta_head {
+	/*
+	 * TODO this is not an RFC 1982 serial. It's supposed to be unbounded,
+	 * so we should probably handle it as a string.
+	 */
 	unsigned long serial;
 	struct doc_data doc_data;
 };
 
 /* List of deltas inside an update notification file */
-struct deltas_head;
+DEFINE_ARRAY_LIST_STRUCT(deltas_head, struct delta_head);
+DECLARE_ARRAY_LIST_FUNCTIONS(deltas_head, struct delta_head)
 
 /* Update notification file content and location URI */
 struct update_notification {
 	struct global_data global_data;
 	struct doc_data snapshot;
-	struct deltas_head *deltas_list;
+	struct deltas_head deltas_list;
 	char *uri;
 };
 
 void global_data_init(struct global_data *);
 void global_data_cleanup(struct global_data *);
 
 void doc_data_init(struct doc_data *);
 void doc_data_cleanup(struct doc_data *);
 
-int update_notification_create(struct update_notification **);
+struct update_notification *update_notification_create(char const *);
 void update_notification_destroy(struct update_notification *);
 
-int delta_head_create(struct delta_head **);
-void delta_head_destroy(struct delta_head *);
-
 typedef int (*delta_head_cb)(struct delta_head *, void *);
 int deltas_head_for_each(struct deltas_head *, unsigned long, unsigned long,
     delta_head_cb, void *);
-int deltas_head_add(struct deltas_head *, unsigned long, unsigned long, char *,
-    unsigned char *, size_t);
-
-int deltas_head_set_size(struct deltas_head *, size_t);
-bool deltas_head_values_set(struct deltas_head *);
+int deltas_head_sort(struct deltas_head *, unsigned long);
 
 int snapshot_create(struct snapshot **);
 void snapshot_destroy(struct snapshot *);
 
 int delta_create(struct delta **);
diff --git a/src/rrdp/rrdp_parser.c b/src/rrdp/rrdp_parser.c
index e1c4428..bc67c0e 100644
--- a/src/rrdp/rrdp_parser.c
+++ b/src/rrdp/rrdp_parser.c
@@ -34,22 +34,10 @@
 #define RRDP_ATTR_SESSION_ID	"session_id"
 #define RRDP_ATTR_SERIAL	"serial"
 #define RRDP_ATTR_URI		"uri"
 #define RRDP_ATTR_HASH		"hash"
 
-/* Array list to get deltas from notification file */
-DEFINE_ARRAY_LIST_STRUCT(deltas_parsed, struct delta_head *);
-DEFINE_ARRAY_LIST_FUNCTIONS(deltas_parsed, struct delta_head *, static)
-
-/* Context while reading an update notification */
-struct rdr_notification_ctx {
-	/* Data being parsed */
-	struct update_notification *notification;
-	/* Unordered list of deltas */
-	struct deltas_parsed deltas;
-};
-
 /* Context while reading a snapshot */
 struct rdr_snapshot_ctx {
 	/* Data being parsed */
 	struct snapshot *snapshot;
 	/* Parent data to validate session ID and serial */
@@ -256,19 +244,21 @@ static int
 parse_string(xmlTextReaderPtr reader, char const *attr, char **result)
 {
 	xmlChar *xml_value;
 	char *tmp;
 
-	if (attr == NULL)
+	if (attr == NULL) {
 		xml_value = xmlTextReaderValue(reader);
-	else
+		if (xml_value == NULL)
+			return pr_val_err("RRDP file: Couldn't find string content from '%s'",
+			    xmlTextReaderConstLocalName(reader));
+	} else {
 		xml_value = xmlTextReaderGetAttribute(reader, BAD_CAST attr);
-
-	if (xml_value == NULL)
-		return pr_val_err("RRDP file: Couldn't find %s from '%s'",
-		    (attr == NULL ? "string content" : "xml attribute"),
-		    xmlTextReaderConstLocalName(reader));
+		if (xml_value == NULL)
+			return pr_val_err("RRDP file: Couldn't find xml attribute '%s' from tag '%s'",
+			    attr, xmlTextReaderConstLocalName(reader));
+	}
 
 	tmp = malloc(xmlStrlen(xml_value) + 1);
 	if (tmp == NULL) {
 		xmlFree(xml_value);
 		return pr_enomem();
@@ -696,183 +686,81 @@ parse_withdraw_elem(xmlTextReaderPtr reader, struct visited_uris *visited_uris)
 		return error;
 
 	return 0;
 }
 
-static int
-rdr_notification_ctx_init(struct rdr_notification_ctx *ctx)
-{
-	deltas_parsed_init(&ctx->deltas);
-	return 0;
-}
-
-static void
-__delta_head_destroy(struct delta_head **delta_head)
-{
-	delta_head_destroy(*delta_head);
-}
-
-static void
-rdr_notification_ctx_cleanup(struct rdr_notification_ctx *ctx)
-{
-	if (ctx->deltas.array != NULL)
-		deltas_parsed_cleanup(&ctx->deltas, __delta_head_destroy);
-}
-
 static int
 parse_notification_delta(xmlTextReaderPtr reader,
-    struct rdr_notification_ctx *ctx)
+    struct update_notification *update)
 {
-	struct delta_head *tmp;
-	unsigned long serial;
+	struct delta_head delta;
 	int error;
 
-	error = delta_head_create(&tmp);
+	error = parse_long(reader, RRDP_ATTR_SERIAL, &delta.serial);
 	if (error)
 		return error;
-
-	error = parse_long(reader, RRDP_ATTR_SERIAL, &serial);
+	error = parse_doc_data(reader, true, true, &delta.doc_data);
 	if (error)
-		goto delta_destroy;
-	tmp->serial = serial;
-
-	error = parse_doc_data(reader, true, true, &tmp->doc_data);
-	if (error)
-		goto delta_destroy;
+		return error;
 
-	error = deltas_parsed_add(&ctx->deltas, &tmp);
+	error = deltas_head_add(&update->deltas_list, &delta);
 	if (error)
-		goto delta_destroy;
+		doc_data_cleanup(&delta.doc_data);
 
-	return 0;
-delta_destroy:
-	delta_head_destroy(tmp);
 	return error;
 }
 
-static int
-order_notification_deltas(struct rdr_notification_ctx *ctx)
-{
-	struct delta_head **ptr;
-	array_index i;
-	int error;
-
-	error = deltas_head_set_size(ctx->notification->deltas_list,
-	    ctx->deltas.len);
-	if (error)
-		return error;
-
-	ARRAYLIST_FOREACH(&ctx->deltas, ptr, i) {
-		error = deltas_head_add(ctx->notification->deltas_list,
-		    ctx->notification->global_data.serial,
-		    (*ptr)->serial,
-		    (*ptr)->doc_data.uri,
-		    (*ptr)->doc_data.hash,
-		    (*ptr)->doc_data.hash_len);
-
-		if (!error)
-			continue;
-
-		if (error == -EINVAL)
-			return pr_val_err("Serial '%lu' at delta elements isn't part of a contiguous list of serials.",
-			    (*ptr)->serial);
-
-		if (error == -EEXIST)
-			return pr_val_err("Duplicated serial '%lu' at delta elements.",
-			    (*ptr)->serial);
-
-		return error;
-	}
-
-	/*
-	 * "If delta elements are included, they MUST form a contiguous
-	 * sequence of serial numbers starting at a revision determined by
-	 * the Repository Server, up to the serial number mentioned in the
-	 * notification element."
-	 *
-	 * If all expected elements are set, everything is ok.
-	 */
-	if (!deltas_head_values_set(ctx->notification->deltas_list))
-		return pr_val_err("Deltas listed don't have a contiguous sequence of serial numbers");
-
-	return 0;
-}
-
 static int
 xml_read_notification(xmlTextReaderPtr reader, void *arg)
 {
-	struct rdr_notification_ctx *ctx = arg;
-	xmlReaderTypes type;
+	struct update_notification *update = arg;
 	xmlChar const *name;
-	int error;
 
-	error = 0;
 	name = xmlTextReaderConstLocalName(reader);
-	type = xmlTextReaderNodeType(reader);
-	switch (type) {
+	switch (xmlTextReaderNodeType(reader)) {
 	case XML_READER_TYPE_ELEMENT:
 		if (xmlStrEqual(name, BAD_CAST RRDP_ELEM_DELTA)) {
-			error = parse_notification_delta(reader, ctx);
+			return parse_notification_delta(reader, update);
 		} else if (xmlStrEqual(name, BAD_CAST RRDP_ELEM_SNAPSHOT)) {
-			error = parse_doc_data(reader, true, true,
-			    &ctx->notification->snapshot);
+			return parse_doc_data(reader, true, true,
+			    &update->snapshot);
 		} else if (xmlStrEqual(name, BAD_CAST RRDP_ELEM_NOTIFICATION)) {
 			/* No need to validate session ID and serial */
-			error = parse_global_data(reader,
-			    &ctx->notification->global_data, NULL, 0);
-			/* Init context for deltas and snapshot */
-			rdr_notification_ctx_init(ctx);
-		} else {
-			return pr_val_err("Unexpected '%s' element", name);
+			return parse_global_data(reader,
+			    &update->global_data, NULL, 0);
 		}
-		break;
+
+		return pr_val_err("Unexpected '%s' element", name);
+
 	case XML_READER_TYPE_END_ELEMENT:
-		if (xmlStrEqual(name, BAD_CAST RRDP_ELEM_NOTIFICATION)) {
-			error = order_notification_deltas(ctx);
-			rdr_notification_ctx_cleanup(ctx);
-			return error; /* Error 0 is ok */
-		}
+		if (xmlStrEqual(name, BAD_CAST RRDP_ELEM_NOTIFICATION))
+			return deltas_head_sort(&update->deltas_list,
+			    update->global_data.serial);
 		break;
-	default:
-		return 0;
-	}
-
-	if (error) {
-		rdr_notification_ctx_cleanup(ctx);
-		return error;
 	}
 
 	return 0;
 }
 
 static int
 parse_notification(struct rpki_uri *uri, struct update_notification **file)
 {
-	struct rdr_notification_ctx ctx;
-	struct update_notification *tmp;
-	char *dup;
+	struct update_notification *result;
 	int error;
 
-	dup = strdup(uri_get_global(uri));
-	if (dup == NULL)
+	result = update_notification_create(uri_get_global(uri));
+	if (result == NULL)
 		return pr_enomem();
 
-	error = update_notification_create(&tmp);
-	if (error)
-		return error;
-
-	tmp->uri = dup;
-
-	ctx.notification = tmp;
 	error = relax_ng_parse(uri_get_local(uri), xml_read_notification,
-	    &ctx);
+	    result);
 	if (error) {
-		update_notification_destroy(tmp);
+		update_notification_destroy(result);
 		return error;
 	}
 
-	*file = tmp;
+	*file = result;
 	return 0;
 }
 
 static int
 xml_read_snapshot(xmlTextReaderPtr reader, void *arg)
@@ -997,12 +885,13 @@ parse_delta(struct rpki_uri *uri, struct delta_head *parents_data,
 	ctx.parent = args->parent;
 	ctx.visited_uris = args->visited_uris;
 	ctx.expected_serial = parents_data->serial;
 	error = relax_ng_parse(uri_get_local(uri), xml_read_delta, &ctx);
 
-	/* Error 0 is ok */
 	delta_destroy(delta);
+	/* Error 0 is ok */
+
 pop_fnstack:
 	fnstack_pop();
 	return error;
 }
 
@@ -1139,8 +1028,8 @@ rrdp_process_deltas(struct update_notification *parent,
 
 	args.parent = parent;
 	args.visited_uris = visited_uris;
 	args.log_operation = log_operation;
 
-	return deltas_head_for_each(parent->deltas_list,
+	return deltas_head_for_each(&parent->deltas_list,
 	    parent->global_data.serial, cur_serial, process_delta, &args);
 }
diff --git a/src/xml/relax_ng.c b/src/xml/relax_ng.c
index a9ad9d0..c35e5a4 100644
--- a/src/xml/relax_ng.c
+++ b/src/xml/relax_ng.c
@@ -107,11 +107,11 @@ relax_ng_parse(const char *path, xml_read_cb cb, void *arg)
 	}
 
 	xmlRelaxNGSetValidErrors(rngvalidctx, relax_ng_log_err,
 	    relax_ng_log_warn, NULL);
 
-	error = xmlTextReaderRelaxNGValidateCtxt(reader, rngvalidctx, 1);
+	error = xmlTextReaderRelaxNGValidateCtxt(reader, rngvalidctx, 0);
 	if (error) {
 		error = pr_val_err("Invalid XML document");
 		goto free_valid_ctx;
 	}
 
diff --git a/test/Makefile.am b/test/Makefile.am
index 08df970..2dc3628 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -22,10 +22,11 @@ MY_LDADD = ${CHECK_LIBS}
 check_PROGRAMS  = address.test
 check_PROGRAMS += deltas_array.test
 check_PROGRAMS += db_table.test
 check_PROGRAMS += line_file.test
 check_PROGRAMS += pdu_handler.test
+check_PROGRAMS += rrdp_objects.test
 check_PROGRAMS += rsync.test
 check_PROGRAMS += serial.test
 check_PROGRAMS += tal.test
 check_PROGRAMS += thread_pool.test
 check_PROGRAMS += vcard.test
@@ -48,10 +49,13 @@ line_file_test_SOURCES = line_file_test.c
 line_file_test_LDADD = ${MY_LDADD}
 
 pdu_handler_test_SOURCES = rtr/pdu_handler_test.c
 pdu_handler_test_LDADD = ${MY_LDADD} ${JANSSON_LIBS}
 
+rrdp_objects_test_SOURCES = rrdp_objects_test.c
+rrdp_objects_test_LDADD = ${MY_LDADD} ${JANSSON_LIBS} ${XML2_LIBS}
+
 rsync_test_SOURCES = rsync_test.c
 rsync_test_LDADD = ${MY_LDADD}
 
 serial_test_SOURCES = serial_test.c
 serial_test_LDADD = ${MY_LDADD}
diff --git a/test/rrdp_objects_test.c b/test/rrdp_objects_test.c
new file mode 100644
index 0000000..d6d41a5
--- /dev/null
+++ b/test/rrdp_objects_test.c
@@ -0,0 +1,117 @@
+#include <check.h>
+#include <errno.h>
+#include <stdlib.h>
+
+#include "impersonator.c"
+#include "log.c"
+#include "rrdp/rrdp_objects.c"
+
+#define END 0xFFFF
+
+static void
+add_serials(struct deltas_head *deltas, ...)
+{
+	struct delta_head delta;
+	va_list vl;
+
+	doc_data_init(&delta.doc_data);
+
+	va_start(vl, deltas);
+	while ((delta.serial = va_arg(vl, unsigned long)) != END)
+		ck_assert_int_eq(0, deltas_head_add(deltas, &delta));
+	va_end(vl);
+}
+
+static void
+validate_serials(struct deltas_head *deltas, ...)
+{
+	unsigned long serial;
+	unsigned int i;
+	va_list vl;
+
+	va_start(vl, deltas);
+
+	i = 0;
+	while ((serial = va_arg(vl, unsigned long)) != END) {
+		ck_assert_uint_eq(serial, deltas->array[i].serial);
+		i++;
+	}
+
+	va_end(vl);
+}
+
+START_TEST(test_deltas_head_sort)
+{
+	struct deltas_head deltas;
+
+	deltas_head_init(&deltas);
+	ck_assert_int_eq(0, deltas_head_sort(&deltas, 0));
+	ck_assert_int_eq(0, deltas_head_sort(&deltas, 1));
+	ck_assert_int_eq(0, deltas_head_sort(&deltas, 2));
+
+	add_serials(&deltas, 0, END);
+	ck_assert_int_eq(0, deltas_head_sort(&deltas, 0));
+	validate_serials(&deltas, 0, END);
+
+	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 2));
+	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 1));
+
+	add_serials(&deltas, 1, 2, 3, END);
+	ck_assert_int_eq(0, deltas_head_sort(&deltas, 3));
+	validate_serials(&deltas, 0, 1, 2, 3, END);
+
+	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 4));
+	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 2));
+
+	deltas_head_cleanup(&deltas, NULL);
+	deltas_head_init(&deltas);
+
+	add_serials(&deltas, 3, 0, 1, 2, END);
+	ck_assert_int_eq(0, deltas_head_sort(&deltas, 3));
+	validate_serials(&deltas, 0, 1, 2, 3, END);
+
+	deltas_head_cleanup(&deltas, NULL);
+	deltas_head_init(&deltas);
+
+	add_serials(&deltas, 4, 3, 2, 1, 0, END);
+	ck_assert_int_eq(0, deltas_head_sort(&deltas, 4));
+	validate_serials(&deltas, 0, 1, 2, 3, 4, END);
+
+	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 5));
+	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 3));
+
+	deltas_head_cleanup(&deltas, NULL);
+}
+END_TEST
+
+Suite *xml_load_suite(void)
+{
+	Suite *suite;
+	TCase *validate;
+
+	validate = tcase_create("Validate");
+	tcase_add_test(validate, test_deltas_head_sort);
+
+	suite = suite_create("xml_test()");
+	suite_add_tcase(suite, validate);
+
+	return suite;
+}
+
+int main(void)
+{
+	Suite *suite;
+	SRunner *runner;
+	int tests_failed;
+
+	log_setup(true);
+
+	suite = xml_load_suite();
+
+	runner = srunner_create(suite);
+	srunner_run_all(runner, CK_NORMAL);
+	tests_failed = srunner_ntests_failed(runner);
+	srunner_free(runner);
+
+	return (tests_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
+}

Vulnerable code: /*
 * List of deltas inside an update notification file.
 *
 * The structure functions are extended and will have the following meaning:
 *   - capacity : is the size of the array, must be set before using the array
 *                and can't be modified.
 *   - len      : number of elements set in the array.
 *
 * This struct is a diff version of array_list, utilized to store only the
 * amount of deltas that may be needed and validate that an update notification
 * file has a contiguous set of deltas.
 */
struct deltas_head {
	/** Unidimensional array. Initialized lazily. */
	struct delta_head **array;
	/** Number of elements in @array. */
	size_t len;
	/** Actual allocated slots in @array. */
	size_t capacity;
};
	data->uri = NULL;
int
delta_head_create(struct delta_head **result)
{
	struct delta_head *tmp;

	tmp = malloc(sizeof(struct delta_head));
	if (tmp == NULL)
		return pr_enomem();

	doc_data_init(&tmp->doc_data);

	*result = tmp;
	return 0;
}

void
delta_head_destroy(struct delta_head *delta_head)
{
	if (delta_head) {
		doc_data_cleanup(&delta_head->doc_data);
		free(delta_head);
	}
}

static void
deltas_head_init(struct deltas_head *list)
{
	list->array = NULL;
	list->len = 0;
	list->capacity = 0;
}

static void
deltas_head_cleanup(struct deltas_head *list)
{
	size_t i;

	for (i = 0; i < list->capacity; i++)
		delta_head_destroy(list->array[i]);
	if (list->array)
		free(list->array);
}

static int
deltas_head_create(struct deltas_head **deltas)
{
	struct deltas_head *tmp;

	tmp = malloc(sizeof(struct deltas_head));
	if (tmp == NULL)
		return pr_enomem();

	deltas_head_init(tmp);

	*deltas = tmp;
	return 0;
}

static void
deltas_head_destroy(struct deltas_head *deltas)
{
	deltas_head_cleanup(deltas);
	free(deltas);
}

int
deltas_head_set_size(struct deltas_head *deltas, size_t capacity)
{
	size_t i;

	if (deltas->array != NULL)
		pr_crit("Size of this list can't be modified");

	deltas->capacity = capacity;
	if (capacity == 0)
		return 0; /* Ok, list can have 0 elements */

	deltas->array = malloc(deltas->capacity
	    * sizeof(struct delta_head *));
	if (deltas->array == NULL)
		return pr_enomem();

	/* Point all elements to NULL */
	for (i = 0; i < deltas->capacity; i++)
		deltas->array[i] = NULL;

	return 0;
}

/*
 * A new delta_head will be allocated at its corresponding position inside
 * @deltas (also its URI and HASH will be allocated). The position is calculated
 * using the difference between @max_serial and @serial.
 *
 * The following errors can be returned due to a wrong @position:
 *   -EEXIST: There's already an element at @position.
 *   -EINVAL: @position can't be inside @deltas list, meaning that such element
 *            isn't part of a contiguous list.
 *
 * Don't forget to call deltas_head_set_size() before this!!
 */
int
deltas_head_add(struct deltas_head *deltas, unsigned long max_serial,
    unsigned long serial, char *uri, unsigned char *hash, size_t hash_len)
{
	struct delta_head *elem;
	size_t position;
	int error;

	position = deltas->capacity - 1 - (max_serial - serial);
	if (position < 0 || position > deltas->capacity - 1)
		return -EINVAL;

	if (deltas->array[position] != NULL)
		return -EEXIST;

	elem = NULL;
	error = delta_head_create(&elem);
	if (error)
		return error;

	elem->serial = serial;

	elem->doc_data.uri = strdup(uri);
	if (elem->doc_data.uri == NULL) {
		free(elem);
		return pr_enomem();
	}

	elem->doc_data.hash_len = hash_len;
	elem->doc_data.hash = malloc(hash_len);
	if (elem->doc_data.hash == NULL) {
		free(elem->doc_data.uri);
		free(elem);
		return pr_enomem();
	}
	memcpy(elem->doc_data.hash, hash, hash_len);

	deltas->array[position] = elem;
	deltas->len++;

	return 0;
}

/* Are all expected values set? */
bool
deltas_head_values_set(struct deltas_head *deltas)
{
	return deltas->len == deltas->capacity;
}

		error = cb(deltas->array[index], arg);
update_notification_create(struct update_notification **file)
	struct update_notification *tmp;
	struct deltas_head *list;
	tmp = malloc(sizeof(struct update_notification));
	if (tmp == NULL)
		return pr_enomem();
	list = NULL;
	error = deltas_head_create(&list);
	if (error) {
		free(tmp);
		return error;
	}
	tmp->deltas_list = list;
	tmp->uri = NULL;
	global_data_init(&tmp->global_data);
	doc_data_init(&tmp->snapshot);
	*file = tmp;
	deltas_head_destroy(file->deltas_list);
struct deltas_head;
	struct deltas_head *deltas_list;
int update_notification_create(struct update_notification **);
int delta_head_create(struct delta_head **);
void delta_head_destroy(struct delta_head *);

int deltas_head_add(struct deltas_head *, unsigned long, unsigned long, char *,
    unsigned char *, size_t);

int deltas_head_set_size(struct deltas_head *, size_t);
bool deltas_head_values_set(struct deltas_head *);
/* Array list to get deltas from notification file */
DEFINE_ARRAY_LIST_STRUCT(deltas_parsed, struct delta_head *);
DEFINE_ARRAY_LIST_FUNCTIONS(deltas_parsed, struct delta_head *, static)

/* Context while reading an update notification */
struct rdr_notification_ctx {
	/* Data being parsed */
	struct update_notification *notification;
	/* Unordered list of deltas */
	struct deltas_parsed deltas;
};

	if (attr == NULL)
	else

	if (xml_value == NULL)
		return pr_val_err("RRDP file: Couldn't find %s from '%s'",
		    (attr == NULL ? "string content" : "xml attribute"),
		    xmlTextReaderConstLocalName(reader));
static int
rdr_notification_ctx_init(struct rdr_notification_ctx *ctx)
{
	deltas_parsed_init(&ctx->deltas);
	return 0;
}

static void
__delta_head_destroy(struct delta_head **delta_head)
{
	delta_head_destroy(*delta_head);
}

static void
rdr_notification_ctx_cleanup(struct rdr_notification_ctx *ctx)
{
	if (ctx->deltas.array != NULL)
		deltas_parsed_cleanup(&ctx->deltas, __delta_head_destroy);
}

    struct rdr_notification_ctx *ctx)
	struct delta_head *tmp;
	unsigned long serial;
	error = delta_head_create(&tmp);

	error = parse_long(reader, RRDP_ATTR_SERIAL, &serial);
		goto delta_destroy;
	tmp->serial = serial;

	error = parse_doc_data(reader, true, true, &tmp->doc_data);
	if (error)
		goto delta_destroy;
	error = deltas_parsed_add(&ctx->deltas, &tmp);
		goto delta_destroy;
	return 0;
delta_destroy:
	delta_head_destroy(tmp);
static int
order_notification_deltas(struct rdr_notification_ctx *ctx)
{
	struct delta_head **ptr;
	array_index i;
	int error;

	error = deltas_head_set_size(ctx->notification->deltas_list,
	    ctx->deltas.len);
	if (error)
		return error;

	ARRAYLIST_FOREACH(&ctx->deltas, ptr, i) {
		error = deltas_head_add(ctx->notification->deltas_list,
		    ctx->notification->global_data.serial,
		    (*ptr)->serial,
		    (*ptr)->doc_data.uri,
		    (*ptr)->doc_data.hash,
		    (*ptr)->doc_data.hash_len);

		if (!error)
			continue;

		if (error == -EINVAL)
			return pr_val_err("Serial '%lu' at delta elements isn't part of a contiguous list of serials.",
			    (*ptr)->serial);

		if (error == -EEXIST)
			return pr_val_err("Duplicated serial '%lu' at delta elements.",
			    (*ptr)->serial);

		return error;
	}

	/*
	 * "If delta elements are included, they MUST form a contiguous
	 * sequence of serial numbers starting at a revision determined by
	 * the Repository Server, up to the serial number mentioned in the
	 * notification element."
	 *
	 * If all expected elements are set, everything is ok.
	 */
	if (!deltas_head_values_set(ctx->notification->deltas_list))
		return pr_val_err("Deltas listed don't have a contiguous sequence of serial numbers");

	return 0;
}

	struct rdr_notification_ctx *ctx = arg;
	xmlReaderTypes type;
	int error;
	error = 0;
	type = xmlTextReaderNodeType(reader);
	switch (type) {
			error = parse_notification_delta(reader, ctx);
			error = parse_doc_data(reader, true, true,
			    &ctx->notification->snapshot);
			error = parse_global_data(reader,
			    &ctx->notification->global_data, NULL, 0);
			/* Init context for deltas and snapshot */
			rdr_notification_ctx_init(ctx);
		} else {
			return pr_val_err("Unexpected '%s' element", name);
		break;
		if (xmlStrEqual(name, BAD_CAST RRDP_ELEM_NOTIFICATION)) {
			error = order_notification_deltas(ctx);
			rdr_notification_ctx_cleanup(ctx);
			return error; /* Error 0 is ok */
		}
	default:
		return 0;
	}

	if (error) {
		rdr_notification_ctx_cleanup(ctx);
		return error;
	struct rdr_notification_ctx ctx;
	struct update_notification *tmp;
	char *dup;
	dup = strdup(uri_get_global(uri));
	if (dup == NULL)
	error = update_notification_create(&tmp);
	if (error)
		return error;

	tmp->uri = dup;

	ctx.notification = tmp;
	    &ctx);
		update_notification_destroy(tmp);
	*file = tmp;
	/* Error 0 is ok */
	return deltas_head_for_each(parent->deltas_list,
	error = xmlTextReaderRelaxNGValidateCtxt(reader, rngvalidctx, 1);
Fixed code: DEFINE_ARRAY_LIST_FUNCTIONS(deltas_head, struct delta_head, )
	data->uri = NULL;
		error = cb(&deltas->array[index], arg);
static int
swap_until_sorted(struct delta_head *deltas, unsigned int i,
    unsigned long min, unsigned long max)
{
	unsigned int target_slot;
	struct delta_head tmp;

	while (true) {
		if (deltas[i].serial < min || max < deltas[i].serial) {
			return pr_val_err("Deltas: Serial '%lu' is out of bounds. (min:%lu, max:%lu)",
			    deltas[i].serial, min, max);
		}

		target_slot = deltas[i].serial - min;
		if (i == target_slot)
			return 0;
		if (deltas[target_slot].serial == deltas[i].serial) {
			return pr_val_err("Deltas: Serial '%lu' is not unique.",
			    deltas[i].serial);
		}

		/* Simple swap */
		tmp = deltas[target_slot];
		deltas[target_slot] = deltas[i];
		deltas[i] = tmp;
	}
}

deltas_head_sort(struct deltas_head *deltas, unsigned long max_serial)
	unsigned long min_serial;
	struct delta_head *cursor;
	array_index i;
	if (max_serial + 1 < deltas->len)
		return pr_val_err("Deltas: Too many deltas (%zu) for serial %lu. (Negative serials not implemented.)",
		    deltas->len, max_serial);
	min_serial = max_serial + 1 - deltas->len;
	ARRAYLIST_FOREACH(deltas, cursor, i) {
		error = swap_until_sorted(deltas->array, i, min_serial,
		    max_serial);
		if (error)
			return error;
	}
struct update_notification *
update_notification_create(char const *uri)
{
	struct update_notification *result;

	result = malloc(sizeof(struct update_notification));
	if (result == NULL)
		return NULL;

	global_data_init(&result->global_data);
	doc_data_init(&result->snapshot);
	deltas_head_init(&result->deltas_list);
	result->uri = strdup(uri);
	if (result->uri == NULL) {
		free(result);
		return NULL;
	}

	return result;
}

static void
delta_head_destroy(struct delta_head *delta)
{
	doc_data_cleanup(&delta->doc_data);
}

	deltas_head_cleanup(&file->deltas_list, delta_head_destroy);
#include "data_structure/array_list.h"
	/*
	 * TODO this is not an RFC 1982 serial. It's supposed to be unbounded,
	 * so we should probably handle it as a string.
	 */
DEFINE_ARRAY_LIST_STRUCT(deltas_head, struct delta_head);
DECLARE_ARRAY_LIST_FUNCTIONS(deltas_head, struct delta_head)
	struct deltas_head deltas_list;
struct update_notification *update_notification_create(char const *);
int deltas_head_sort(struct deltas_head *, unsigned long);
	if (attr == NULL) {
		if (xml_value == NULL)
			return pr_val_err("RRDP file: Couldn't find string content from '%s'",
			    xmlTextReaderConstLocalName(reader));
	} else {
		if (xml_value == NULL)
			return pr_val_err("RRDP file: Couldn't find xml attribute '%s' from tag '%s'",
			    attr, xmlTextReaderConstLocalName(reader));
	}
    struct update_notification *update)
	struct delta_head delta;
	error = parse_long(reader, RRDP_ATTR_SERIAL, &delta.serial);
	error = parse_doc_data(reader, true, true, &delta.doc_data);
		return error;
	error = deltas_head_add(&update->deltas_list, &delta);
		doc_data_cleanup(&delta.doc_data);
	struct update_notification *update = arg;
	switch (xmlTextReaderNodeType(reader)) {
			return parse_notification_delta(reader, update);
			return parse_doc_data(reader, true, true,
			    &update->snapshot);
			return parse_global_data(reader,
			    &update->global_data, NULL, 0);

		return pr_val_err("Unexpected '%s' element", name);

		if (xmlStrEqual(name, BAD_CAST RRDP_ELEM_NOTIFICATION))
			return deltas_head_sort(&update->deltas_list,
			    update->global_data.serial);
	struct update_notification *result;
	result = update_notification_create(uri_get_global(uri));
	if (result == NULL)
	    result);
		update_notification_destroy(result);
	*file = result;
	/* Error 0 is ok */

	return deltas_head_for_each(&parent->deltas_list,
	error = xmlTextReaderRelaxNGValidateCtxt(reader, rngvalidctx, 0);
check_PROGRAMS += rrdp_objects.test
rrdp_objects_test_SOURCES = rrdp_objects_test.c
rrdp_objects_test_LDADD = ${MY_LDADD} ${JANSSON_LIBS} ${XML2_LIBS}

#include <check.h>
#include <errno.h>
#include <stdlib.h>

#include "impersonator.c"
#include "log.c"
#include "rrdp/rrdp_objects.c"

#define END 0xFFFF

static void
add_serials(struct deltas_head *deltas, ...)
{
	struct delta_head delta;
	va_list vl;

	doc_data_init(&delta.doc_data);

	va_start(vl, deltas);
	while ((delta.serial = va_arg(vl, unsigned long)) != END)
		ck_assert_int_eq(0, deltas_head_add(deltas, &delta));
	va_end(vl);
}

static void
validate_serials(struct deltas_head *deltas, ...)
{
	unsigned long serial;
	unsigned int i;
	va_list vl;

	va_start(vl, deltas);

	i = 0;
	while ((serial = va_arg(vl, unsigned long)) != END) {
		ck_assert_uint_eq(serial, deltas->array[i].serial);
		i++;
	}

	va_end(vl);
}

START_TEST(test_deltas_head_sort)
{
	struct deltas_head deltas;

	deltas_head_init(&deltas);
	ck_assert_int_eq(0, deltas_head_sort(&deltas, 0));
	ck_assert_int_eq(0, deltas_head_sort(&deltas, 1));
	ck_assert_int_eq(0, deltas_head_sort(&deltas, 2));

	add_serials(&deltas, 0, END);
	ck_assert_int_eq(0, deltas_head_sort(&deltas, 0));
	validate_serials(&deltas, 0, END);

	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 2));
	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 1));

	add_serials(&deltas, 1, 2, 3, END);
	ck_assert_int_eq(0, deltas_head_sort(&deltas, 3));
	validate_serials(&deltas, 0, 1, 2, 3, END);

	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 4));
	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 2));

	deltas_head_cleanup(&deltas, NULL);
	deltas_head_init(&deltas);

	add_serials(&deltas, 3, 0, 1, 2, END);
	ck_assert_int_eq(0, deltas_head_sort(&deltas, 3));
	validate_serials(&deltas, 0, 1, 2, 3, END);

	deltas_head_cleanup(&deltas, NULL);
	deltas_head_init(&deltas);

	add_serials(&deltas, 4, 3, 2, 1, 0, END);
	ck_assert_int_eq(0, deltas_head_sort(&deltas, 4));
	validate_serials(&deltas, 0, 1, 2, 3, 4, END);

	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 5));
	ck_assert_int_eq(-EINVAL, deltas_head_sort(&deltas, 3));

	deltas_head_cleanup(&deltas, NULL);
}
END_TEST

Suite *xml_load_suite(void)
{
	Suite *suite;
	TCase *validate;

	validate = tcase_create("Validate");
	tcase_add_test(validate, test_deltas_head_sort);

	suite = suite_create("xml_test()");
	suite_add_tcase(suite, validate);

	return suite;
}

int main(void)
{
	Suite *suite;
	SRunner *runner;
	int tests_failed;

	log_setup(true);

	suite = xml_load_suite();

	runner = srunner_create(suite);
	srunner_run_all(runner, CK_NORMAL);
	tests_failed = srunner_ntests_failed(runner);
	srunner_free(runner);

	return (tests_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
}