D array expansion and non-deterministic re-allocation

[dsimcha]

== Quote from Bartosz Milewski (bartosz-nospam at relisoft.com)'s article
> I read Andrei's chapter on arrays and there's one thing that concerns me. When a
slice is extended, the decision to re-allocate, and therefore to cut its
connection to other slices, is non-deterministic. How does that influence program
testing and can it be exploited to attack a buggy system?
> Here's a piece of code I came up with--it's not realistic but it describes a
certain class of scenarios:
> void f(byte[] code)
> {
>     doSomeChecks(code);
>     execute(code);
> }
> void doSomeChecks(byte[] a)
> {
>    …
>   // to avoid special-casing empty arrays
>   a.length += 1; // extension
>    …
>   // get byte b (or a whole bunch) from somewhere
>    a[0] = b; // write
>   …
>   // check what happens when a[0] = b
> }
> Of course this code is incorrect because doSomeChecks assumes that it holds a
unique array, and the caller failed to make a copy before sending it to
doSomeChecks. Bad bad programmer!
> However imagine this scenario: Under testing conditions, the array extension
just happens to always cause reallocation, so the write is NOT visible in the
calling routine. All tests pass with flying colors. But since the re-allocation
is, by language definition, non-deterministic, it might happen that, after the
code has been deployed, the re-allocation stopped happening, say, on Sundays. If a
hacker learns about that, he may be able to inject malicious code or data into the
program.
> In this case the non-determinism built into the language helped camouflage a
serious bug. Should we, or shouldn't we, worry about it in practice?

The one thing that I think has been missing from this discussion is, what would be
the alternative if we didn't have this "non-deterministic" reallocation?  How else
could you **efficiently** implement dynamic arrays?