Possibly serious bugs in add_item_to_array in 1.7.13

[SLDiggie]

From 1.7.12 -> 1.7.13 this code was changed in add_item_to_array:

`
static cJSON_bool add_item_to_array(cJSON *array, cJSON *item)
{
cJSON *child = NULL;

if ((item == NULL) || (array == NULL))
{
    return false;
}

child = array->child;

if (child == NULL)
{
    /* list is empty, start new one */
    array->child = item;
}
else
{
    /* append to the end */
    while (child->next)
    {
        child = child->next;
    }
    suffix_object(child, item);
}

return true;

}
`

->

`
static cJSON_bool add_item_to_array(cJSON *array, cJSON *item)
{
cJSON *child = NULL;

if ((item == NULL) || (array == NULL) || (array == item))
{
    return false;
}

child = array->child;
/*
 * To find the last item in array quickly, we use prev in array
 */
if (child == NULL)
{
    /* list is empty, start new one */
    array->child = item;
    item->prev = item;
    item->next = NULL;
}
else
{
    /* append to the end */
    if (child->prev)
    {
        suffix_object(child->prev, item);
        array->child->prev = item;
    }
    else
    {
        while (child->next)
        {
            child = child->next;
        }
        suffix_object(child, item);
        array->child->prev = item;
    }
}

return true;

}
`

The new code seems very strange:

• If array has no child, the old code assigns the new item as the child. The new code for some reason also sets the new item's prev pointer to point at itself. If prev is traversed, that is an infinite loop.

• In the old code, to add a new item to the end of a child, the code follows the pointers chain to all the next child items, then adds the new item at the end. The new code seems to make two errors:

(1) Assuming child must be the first child item in array, if the new code sees a prev pointer on this first child it tries to add the new item to it, i.e. before the first child. You end up in a situation where you can't start at the first child and follow Next to the new element, you instead have to start at the first child then go Prev then go Next. A result of this is that code that traverses the pointers via Next doesn't see all of the values. For example, print() will not include them. We run into this bug when constructing an object tree with more than one item in the array with cJSON, only in 1.7.13.

(2) If child->prev is null it makes the old last item's prev point at the new item. The old last item's next ALSO points at the last item (due to suffix_object). Traversing prev for the last two items will now infinitely loop between the last two items.

These seem like serious issues, as you end up with potential infinite loops and values you expect missing from the output when you build a document tree with cJSON, even though no errors are returned.

[SLDiggie]

I see that in 1.7.13 there is a changelog note, "Improve performance of adding item to array.". This seems to have been implemented by "abusing" the "prev" pointer in an attempt to turn the double-linked list into a circular buffer, creating an infinite loop on prev, and redefining the meaning of prev for cJSON_Array in the data structure documentation. That documentation has been static for many years and likely relied upon by many developers.

For most of history:

This is implemented by pointing child to a linked list of cJSON items that represent the values in the array. The elements are linked together using next and prev, where the first element has prev == NULL and the last element next == NULL.

New for 1.7.13:

This is implemented by pointing child to a linked list of cJSON items that represent the values in the array. The elements are linked together using next and prev, where the first element has prev.next == NULL and the last element next == NULL.

You need to dereference what was previously a null pointer to test if you're at the start.

This is IMO a really bad design choice. If it's important to provide fast access to the end of the double-linked list, why not add a new member to the cJSON structure that points to it, and maintain full backwards compatibility/semantics, as well as the normall expected behavior of a double-linked list?

[Alanscut]

@SLDiggie Thanks your reporting, the reason why the tail node is not added in the cJSON struct is that we value space very much, as you said, which is not a good choice, as you said. I'll release a new version to fix these problems before the end of September.

[SLDiggie]

@Alanscut Just to be clear, I'm not only reporting the design issue, but the changes in cJSON 1.7.13 also seem to create the potential for use after free vulnerabilities (might be a crash and/or security issue), erroneous document output, and DOS (infinite loops). IMO you ought to be considering reverting some of these.

I made a small sample function to help illustrate, hopefully that's useful to you. None of these problems happen against 1.7.12.

`
void TestcJSON()
{

/*

Sample doc looks like this:

{
    "objA": {
        "name_a1": "val_a1",
        "name_a2": "val_a2",
        "name_a3": "val_a3"
    },
    "objB": {
        "name_b1": "val_b1",
        "name_b2": "val_b2",
        "name_b3": "val_b3"
    }
}

*/

// Load the sample doc
const char* szInDoc = "{\"objA\":{\"name_a1\":\"val_a1\",\"name_a2\":\"val_a2\",\"name_a3\":\"val_a3\"},\"objB\":{\"name_b1\":\"val_b1\",\"name_b2\":\"val_b2\",\"name_b3\":\"val_b3\"}}";
cJSON *json = cJSON_Parse(szInDoc);

cJSON *objC = cJSON_CreateObject();
cJSON_AddItemToObject(json, "objC", objC);

// Add an array to objC
// This part works as expected
cJSON *new_array = cJSON_CreateArray();
cJSON *array_item = cJSON_CreateString("val_c1a");
cJSON_AddItemToArray(new_array, array_item);
cJSON_AddItemToObject(objC, "name_c1", new_array);


// Now replace the array in objC
// This part breaks in 1.7.13 because cJSON_ReplaceItemViaPointer copies prev and next from the old item to the replacement item,
// and prev points at the old item. That's possibly a use after free vulnerability, because the calling code could free the memory it after replacement.
// For example, among other things, cJSON itself might later dereference it to test prev->next.
cJSON *new_array2 = cJSON_CreateArray();
cJSON *array_item2 = cJSON_CreateString("val_c1b");
cJSON_AddItemToArray(new_array2, array_item2);
cJSON_ReplaceItemInObject(objC, "name_c1", new_array2);


// Due to the above bug, assuming a use after free isn't triggered, add_item_to_array is going to add this
// new item to the item that was replaced (still referenced in prev). It therefore exists somehow in memory
// but it will never be seen by any code that traverses an array using the chain of next pointers
cJSON *new_item = cJSON_CreateNumber(1234);
cJSON_AddItemToObject(objC, "name_c2", new_item);

// If we print the document, "name_c2" will be completely missing from objC due to this issue
char *updated_json = cJSON_Print(json);

// Now create a new array to work with
cJSON *new_array3 = cJSON_CreateArray();
for (auto i = 1; i <= 3; i++)
{
	cJSON *cjson_string = cJSON_CreateString((std::string("val_d") + std::to_string(i)).c_str());
	cJSON_AddItemToArray(new_array3, cjson_string);
}


// Traverse the array forwards then backwards
{
	// Count elements following next pointers
	// This also finds the last element of the array
	int i = 0;
	cJSON *item = new_array3->child;
	if (item)
	{
		do
		{
			i++;
			if (item->next)
				item = item->next;
			else
				break;
		} while (true);
	}
	

	// Now traverse backward through the linked list
	// In cJSON 1.7.13 this will be an infinite loop for any program that expects prev == NULL 
	// to be the start of the array, per the documenation for 1.7.12 and earlier.
	i = 0;
	while (item)
	{
		i++;
		item = item->prev;
	}

}

}
`

[Alanscut]

@SLDiggie

• question1: "name_c2" will be completely missing from objC due to this issue

this issue has been fixed by #456 , and I have tested your case, it works well.

• question2: traverse backward through the linked list will cause infinite loop

this is not an issue of cJSON, I will update the doc so as not to mislead others. the infinite loop is caused by the wrong while condition, once the head->pre = tail, the item will never be null.

IMHO, we can improve efficiency safely in the current way, but I have to admit that this is not a conventional approach. Even if we change it to a full double linked list, the second problem you mentioned above still exists. So, would you prefer to add a node to cJSON struct to record the tail node?