Seralize incorrectly duplicates element in case of circular reference in array

[IceNV]

Description

The following code:

<?php

$a = ['id'=>1,'parent'=>null,'child'=>null];
$b = ['id'=>2,'parent'=>null,'child'=>null];
$a['child'] =&$b;
$b['parent'] = &$a;
echo serialize($a);

Resulted in this output:

a:3:{s:2:"id";i:1;s:6:"parent";N;s:5:"child";a:3:{s:2:"id";i:2;s:6:"parent";a:3:{s:2:"id";i:1;s:6:"parent";N;s:5:"child";R:4;}s:5:"child";N;}}

The problem is that in the 'child' array with id 2, 'parent' duplicates the root array with id 1 instead of directly referencing it, something along the lines of :

a:3:{s:2:"id";i:1;s:6:"parent";N;s:5:"child";a:3:{s:2:"id";i:2;s:6:"parent";R:1;s:5:"child";N;}}

In any case, the parent array shouldn't be duplicated, as this can cause traversal issues or modifications that won't properly propagate if code tries to modify the de-serialized array (for instance modifying element 2's parent will not propagate to the root as it should), for instance :

If I modify the original array :

$a['id'] = 3;
echo($a['id'].','.$a['child']['parent']['id']);

echoes (properly) :

3,3

However, if I unserialize the aformentioned string, and apply the same operation, it echoes :

3,1

The reference is lost, as is apparent from the serialized form.

(Of course this is a trivial example but corresponds to something I've encountered working with graph-type arrays)

PHP Version

PHP 8.1.21 (FPM,CLI)

Operating System

Debian 10 x64 (on WSL2 on Windows 10 x64) ; Debian 11 x64 (native)

[IceNV]

I've tried to diagnose the problem a bit further.

If I try instead, following the previous example, and reusing its $a and $b, to include them in an array, preserving references, it seems to work :

$c = [
	&$a,
	&$b
];
echo serialize($c);

Outputs the following :

a:2:{i:0;a:3:{s:2:"id";i:1;s:6:"parent";N;s:5:"child";a:3:{s:2:"id";i:2;s:6:"parent";R:2;s:5:"child";N;}}i:1;R:5;}

Even just including the single parent element in an array seems to work also :

$c = [
	&$a,
];
echo serialize($c);

Outputs :

a:1:{i:0;a:3:{s:2:"id";i:1;s:6:"parent";N;s:5:"child";a:3:{s:2:"id";i:2;s:6:"parent";R:2;s:5:"child";N;}}}

I suspect that because the input of serialize(), being an array, is passed as a copy (which makes sense, so as to not destroy the original variable), that causes internal/circular references to the root variable to break because they're pointing to the original variable instead of the copy that serves as the input parameter.

This would also explain that when I do this :

$c = [
	$a,
];
echo serialize($c);

I get this :

a:1:{i:0;a:3:{s:2:"id";i:1;s:6:"parent";N;s:5:"child";a:3:{s:2:"id";i:2;s:6:"parent";a:3:{s:2:"id";i:1;s:6:"parent";N;s:5:"child";R:5;}s:5:"child";N;}}}

Which has the same problem as the original. The array is copied (in this last example, manually by the code ; otherwise, by serialize()) then traversed from the root, creating copies of the values until it hits a reference, which then gets pulled from the original reference and gets duplicated.
Internal references already all come from the original variable as they are not passed directly, so they don't exhibit the problem.

[iluuu1994]

This is a know issue, see #11349 (comment). Do you have an actual use case for serialization of recursive arrays or did you find this by playing around?

[IceNV]

I see. As I feared this is a problem without a "correct" solution, as you mentioned in that comment.

This was found during development of a security layer internal to our application that applies integrity checks to objects post-deserialization, and thus traverses deserialized arrays recursively in case they contain such objects. We do also have recursive/circular arrays, although they're not serialized for now, so I don't have an immediate use case.

If the workaround is to detect recursive arrays and wrap them in an "outer" array or object at serialization time, we could implement a serialization wrapper for that ; this leads to the problem of detecting recursive arrays, since unlike objects, we just cant use === or spl_object_hash or any built-in (AFAIK), it is still doable but a bit tricky to optimize.

In that case, maybe the documentation for serialize() should mention this particular case ?

[iluuu1994]

We do also have recursive/circular arrays

Can you explain your use-case more? But I'm afraid you'll most likely be better off using some object list type for recursive structures, as there is much better support for recursion with serialize there.

In that case, maybe the documentation for serialize() should mention this particular case ?

Documenting this is fine, but the technical details may be hard to grasp.

[IceNV]

Can you explain your use-case more? But I'm afraid you'll most likely be better off using some object list type for recursive structures, as there is much better support for recursion with serialize there.

It is a tree-style graph, where child nodes also have a reference to parent node for optimization purposes. Some do reference the root node.
I agree about changing it to objects,it is probably what we'll do in time.
For now, what I've done is remove the 'parent' references before serializing and rebuild them post deserialization. So there definitely are work-arounds, but developers have to be aware of the problem to implement them.

Documenting this is fine, but the technical details may be hard to grasp.

I get that. Maybe with minimal examples ? Something like :

---

Notice : Arrays containing references to themselves

Because the argument to serialize() is passed by copy for non-object values, passing an array that contains references to itself will produce an inside copy of the array.

This is because the array being passed by copy, the root of the serialized array is the newly-created copy, whereas the inner references point to the original array.

This effectively breaks references to the main array. For instance :

// Define a recursive array where A and B reference each other through their 'ref' property
$a = ['id'=>1,'ref'=>null];
$b = ['id'=>2,'ref'=>&$a];
$a['ref'] = &$b;

// Check that references work
	// Modify a value directly
	$a['id'] = 3;
	// Check their circular reference
	var_dump($a['id']); // Direct access outputs 3
	var_dump($a['ref']['ref']['id']); // Indirect access (a->b->a) outputs 3 properly 

// Serialize
	$s = serialize($a);
	var_dump($s); // Outputs the serialized form, where there are two instances of an element with id 3

// Unserialize
	$c = unserialize($s);

// Check that references are broken
	// Modify values directly
	$c['id'] = 4;
	// Check their circular reference
	var_dump($c['id']); // Direct access outputs 4
	var_dump($c['ref']['ref']['id']); // Indirect access (a->b->a) will still output 3 instead of 4, because really it's (a_copy->b->a)

Outputs

int 3
int 3
string 'a:2:{s:2:"id";i:3;s:3:"ref";a:2:{s:2:"id";i:2;s:3:"ref";a:2:{s:2:"id";i:3;s:3:"ref";R:3;}}}' (length=91)
int 4
int 3

On the other hand, references that point to elements inside the array but not the array to be serialized itself are preserved, for example :

// Define a recursive array where A and B reference each other through their 'ref' property
	$a = ['id'=>1,'ref'=>null];
	$b = ['id'=>2,'ref'=>&$a];
	$a['ref'] = &$b;
// But this time include them in a 'parent' array
	$c = [
		1=>&$a,
		2=>&$b,
	];

// Check that references work
	// Modify a value directly
		$c[1]['id'] = 3;
	// Check their circular reference
		var_dump($c[1]['id']); // Direct access outputs 3
		var_dump($c[1]['ref']['ref']['id']); // Indirect access (a->b->a) outputs 3 properly

// Serialize
	$s = serialize($c);
	var_dump($s); // Outputs the serialized form, where there are no double instances

// Unserialize
	$d = unserialize($s);

// Check that references are broken
	// Modify values directly
		$d[1]['id'] = 4;
	// Check their circular reference
		var_dump($d[1]['id']); // Direct access outputs 4
		var_dump($d[1]['ref']['ref']['id']); // Indirect access (a->b->a) still works and outputs 4

Outputs :

int 3
int 3
string 'a:2:{i:1;a:2:{s:2:"id";i:3;s:3:"ref";a:2:{s:2:"id";i:2;s:3:"ref";R:2;}}i:2;R:4;}' (length=80)
int 4
int 4

Objects are always passed by reference and are not affected. Other primitive types cannot hold inner references and are not affected either.

---

However, after writing it, I see that, even though I tried to be as concise as possible, it's still a long example, and maybe would confuse users who don't need that piece of information. It's still useful to know about that particular case, but I wouldn't know where to put it in the documentation.

[iluuu1994]

Because the argument to serialize() is passed by copy for non-object values, passing an array that contains references to itself will produce an inside copy of the array.

I believe this is not entirely accurate. What happens is that we unwrap the reference, thus passing the array instead of the reference that holds the array. Because arrays have CoW semantics, they are only actually copied once they are modified. This means that two places may refer to the same array but treat them as separate. For example, $a = ['foo']; $b = [$a, $a]; should treat $b as an array containing two distinct array instead of an array containing the same array twice, even though that's what is happening under the hood. Moreover, we may have to separate references containing references to the same array. The same applies here, we should treat the arrays as separate. This scenario can occur with $a = ['foo']; $b = $a; $a2 = &$a; $b2 = &$b;. $a2 and $b2 now contain a separate reference to the same underlying array. If we encounter an array without knowing what reference it originates from, we cannot now whether two references were intended to reference the same array, or whether they just happened to share the underlying memory.

I think we could fix this issue by using converting the parameter to be passed by-ref with @prefer-ref to maintain backwards compatibility. However, this would likely have a negative performance impact due to reference allocation when it is unnecessary for anything except this edge-case.

[IceNV]

I see. I tried to keep it short, but was indeed imprecise. Such a finely detailed technical explanation is complex to sum up. The documentation could just include a warning not to do that, but it would leave users wanting to know why, so it's not ideal either.

I am not well-versed enough in the internals of the PHP engine to know what kind of performance impact this would have, but generally agree that it would not be desirable.

(For now, in addition to the initial workaround, I've wrapped all calls to serialize() in our framework (in development environment, where performance is not critical) inside a function that detects this particular case and throws a specific exception if it happens, letting the developers (myself included) know they need to work around it.)

Should I close this ?