#249 SuggestMgr::lcs reads from uninitialized memory

[Rachel Blum]

SuggestMgr::lcs uses malloc twice:

c = (char ) malloc((m + 1) * (n + 1));
b = (char ) malloc((m + 1) * (n + 1));

c is never fully initialized - (m(n+1))...((m+1)(n+1)-1) is not initialized. Furthermore, malloc in this form is susceptible to overflows.

Suggested patch: Replace malloc with calloc. (Patch attached)

[Németh László]

This longest common substring algorithm initializes c row by row in its main loop, see https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Solution_for_two_sequences.

Thanks for your feedback.

[Rachel Blum]

It theoretically should indeed, but it doesn't seem to. There's evidence of uninitialized reads from Chromium's leakchecker - see https://code.google.com/p/chromium/issues/detail?id=377728

I agree that on inspection the code seems correct.

[Rachel Blum]

Follow up: The original code triggers a compiler issue in VS2013SP2 - see the chromium bug link above. The initialization loop - for (i = 1; i <= m; i++) c[i*(n+1)] = 0; - does 0-initialize with a stride of 1 instead of (n+1).

The patch (update attached) removes the code that triggers the compiler issue.

[Rachel Blum]

See https://connect.microsoft.com/VisualStudio/feedback/details/884275/vs2013-c-compiler-ignores-loop-stride-and-writes-the-wrong-memory-locations for the MS bug.