Extension check, ply and crash

[Pedro Castro]

In this position, wac 237, Black receive a value of mate -9999 (- MATE) in depth 15 and 1:10 s, which is impossible, if I am not in check, is my turn, I cannot receive mate. Then, program crash.

r5k1/pQp2qpp/8/4pbN1/3P4/6P1/PPr4P/1K1R3R b - - 0 1

[diag]r5k1/pQp2qpp/8/4pbN1/3P4/6P1/PPr4P/1K1R3R b - - 0 1 [/diag]

11484945<1:1 109 0 364 c2h2 g5e4
11484945<1:2 104 0 1615 c2h2 g5e4 f5e4 b7e4
11484975<1:3 89 3 14825 c2h2 g5e4 f5e4 b7e4
11484995<1:3 -34 5 23250 f7e8 b7d5 g8f8 d4e5 c2h2
11485065<1:4 -43 12 64838 f7e8 b7b3 g8f8 g5e6 f8g8 e6c7 c2c4 b1a1
11485255<1:5 -58 31 218461 f7e8 b7b3 g8f8 g5e6 f8g8 e6c7 c2c4 b1a1
11485465<1:5 -92 52 379071 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 e5e4
11485746<1:6 -107 80 588679 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 e5e4
11486006<1:6 -108 107 799582 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 f5g4 d1f1
11486587<1:7 -94 165 1242843 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 f5c2 d1f1 e5e4
11487398<1:8 -79 245 1859457 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 f5c2 d1f1 e5e4
11487588<1:8 7 264 1987146 c2c5 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1f1 a8e8 h2h3
11489631<1:9 12 469 3627470 c2c5 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5
11495019<1:10 27 1007 7838004 c2c1 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5
11495039<1:10 177 1010 7848223 c2c1 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5
11495330<1:10 220 1038 8076405 c2c1 b1c1 f7c4 c1d2 c4d3 d2e1 d3e3 e1f1 a8f8 f1g2 e3e2 g2g1 e2d1 g1g2 d1d2 g2g1 d2e3 g1f1 e3g5 d4e5
11499295<1:11 235 1435 11880197 c2c1
11500847<1:11 362 1591 13066342 c2c1 b1c1 f7c4 c1d2 c4d3 d2e1 d3e3 e1f1 a8f8 f1g2 e3e2 g2g1 e2d1 g1g2 d1d2 g2g1 d2d4 g1g2 d4d2 g2g1 d2g5 b7a7
11507137<1:12 369 2220 18818340 c2c1 b1c1 f7c4 c1d2 c4d3 d2e1 d3e3 e1f1 a8f8 f1g2 e3e2 g2g1 e2d1 g1g2 d1d2 g2g1 d2d4 g1g2 d4d2 g2g1 d2c1 g1g2 c1g5 b7a7
11515489<1:13 369 3009 25629959 c2c1 b1c1 f7c4 c1d2 c4d3 d2e1 d3e3 e1f1 a8f8 f1g2 e3e2 g2g1 e2d1 g1g2 d1d2 g2g1 d2d4 g1g2 d4d2 g2g1 d2c1 g1g2 c1g5 b7a7
11524041<1:14 384 3909 32944296 c2c1 b1c1 f7c4 c1d2 c4d3 d2e1 d3e3 e1f1 a8f8 f1g2 e3e2 g2g1 e2d1 g1g2 d1d2 g2g1 d2d4 g1g2 d4d2 g2g1 d2c1 g1g2 c1g5 b7a7
11530520<1:14 401 4558 38099569 c2c1 b1c1 f7c4 c1d2 c4d3 d2e1 d3e3 e1f1 a8f8 f1g2 e3e2 g2g1 f5e6 g5f3 e2d1 g1g2 d1e2 g2g1 e5d4 b7c7 e2e3 g1g2 e3f3
11540815<1:15 416 5588 47212665 c2c1
11541165<1:15 566 5622 47380711 c2c1
11543709<1:15 386 5877 49457070 c2c1
11543719<1:15 -9999 5877 49457071 ??????????????????????
11543729<1:15 -9999 5877 49457072
11543739<1:15 -9999 5877 49457073
1543739<1:move c2c1
11543749*1*Mov. encontrado:Tc2-c1
11543929<1:1-0 {White mates}
11543939*1*black resigns detected...
11543949<1:1 -9999 0 1
11543959<1:1 -9999 0 2
11543959<1:move c2c1
11543970<1:1-0 {White mates}
11543970*1*black resigns detected...
11543990<1:1 -9999 0 1
11543990<1:1 -9999 0 2

If I clear the extension of check, the program does not receive value
-9999, arrives more at depth 20 and it does not do crash.

I have seen in some program that limits ply, ej TSCP
if (ply > MAX_PLY - 1)
return eval();
This continues failing for my, the peculiar thing is that if I do
if (ply > MAX_PLY/2 - 1)
the thing works well.

If I apply same hash tables to TSCP, the program does not do crash and it does not receive value -9999.

Some idea?

Thank you

[Alessandro Scotti]

Hi Pedro,
I had this same bug in Kiwi. It is probably caused by overflowing an array where you use the ply as an index. It can be the killer move table, or the search tree "history" (e.g. for detecting 3-reps) or something like that.

[Tord Romstad]

Hi Pedro!

In this position, wac 237, Black receive a value of mate -9999 (- MATE) in depth 15 and 1:10 s, which is impossible, if I am not in check, is my turn, I cannot receive mate. Then, program crash.

r5k1/pQp2qpp/8/4pbN1/3P4/6P1/PPr4P/1K1R3R b - - 0 1

[diag]r5k1/pQp2qpp/8/4pbN1/3P4/6P1/PPr4P/1K1R3R b - - 0 1 [/diag]

11484945<1:1 109 0 364 c2h2 g5e4
11484945<1:2 104 0 1615 c2h2 g5e4 f5e4 b7e4
11484975<1:3 89 3 14825 c2h2 g5e4 f5e4 b7e4
11484995<1:3 -34 5 23250 f7e8 b7d5 g8f8 d4e5 c2h2
11485065<1:4 -43 12 64838 f7e8 b7b3 g8f8 g5e6 f8g8 e6c7 c2c4 b1a1
11485255<1:5 -58 31 218461 f7e8 b7b3 g8f8 g5e6 f8g8 e6c7 c2c4 b1a1
11485465<1:5 -92 52 379071 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 e5e4
11485746<1:6 -107 80 588679 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 e5e4
11486006<1:6 -108 107 799582 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 f5g4 d1f1
11486587<1:7 -94 165 1242843 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 f5c2 d1f1 e5e4
11487398<1:8 -79 245 1859457 c2c5 b1a1 f7d5 b7a8 d5a8 d4c5 f5c2 d1f1 e5e4
11487588<1:8 7 264 1987146 c2c5 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1f1 a8e8 h2h3
11489631<1:9 12 469 3627470 c2c5 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5
11495019<1:10 27 1007 7838004 c2c1 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5
11495039<1:10 177 1010 7848223 c2c1 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5

I'm not sure how much this helps, but perhaps you should look for a bug earlier in the search than the - MATE score at depth 15. The last two PVs above are obviously wrong, and contain several illegal moves.

I have seen in some program that limits ply, ej TSCP
if (ply > MAX_PLY - 1)
return eval();
This continues failing for my, the peculiar thing is that if I do
if (ply > MAX_PLY/2 - 1)
the thing works well.

Very strange. Is it possible that you try to access some array with MAX_PLY elements, and that your array index is accidentally incremented and decremented by 2 rather than 1 when you make and unmake moves?

At any rate, it sounds like you have an array out of bounds bug somewhere. If your C compiler supports some kind of optional bounds checking, switch it on, recompile your program, and run WAC237 again. Of course your program will run much more slowly than usual, but with some luck you will get a meaningful error message which helps you to track down your bug.

Tord

[Pedro Castro]

Hi Alessandro and Tord!

the one that Alessandro had the same error in kiwi has helped me much, it seems that the error I also had it in the array of the killers moves.

Thank you,

[Pedro Castro]

Hi Tord,

I have found the problem also in the PV, if you pay attention the PV is equal in depth 9 and 10, except for the first move, when I returned a value of the tables hash, only changed the first value of the previous PV.

11489631<1:9 12 469 3627470 c2c5 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5
11495019<1:10 27 1007 7838004 c2c1 b1a1 f7d5 b7d5 c5d5 d4e5 d5e5 h1e1 a8e8 e1e5 e8e5

I believe that if post the analysis of the other 299 positions of wac, would find 299x2 more = 598 errors.

[Anonymous]

I have seen in some program that limits ply, ej TSCP
if (ply > MAX_PLY - 1)
return eval();
This continues failing for my, the peculiar thing is that if I do
if (ply > MAX_PLY/2 - 1)
the thing works well.

Very strange. Is it possible that you try to access some array with MAX_PLY elements, and that your array index is accidentally incremented and decremented by 2 rather than 1 when you make and unmake moves?

At any rate, it sounds like you have an array out of bounds bug somewhere. If your C compiler supports some kind of optional bounds checking, switch it on, recompile your program, and run WAC237 again.

I just grepped for MAXPLY in my sources. Several parts depend on MAXPLY, not only the PV. At first glance I saw killer moves, move list and several internal Yace specific tables. One would also need to take care of filling the PV after a hash cutoff. I use an end marker in several arrays (like the ones used for the PV), so one has to be aware of that additional entry needed for the endmarker (and also make sure, that the endmarker is always there, which might not be the case, when just returning eval).

It should be a good idea, to always (in debug mode) check PV moves for legality. One could also plug in such code, at the time, any move is written to the PV array, not only when actually formating it for output. This way, one should be able to find the spot of the problem easier (with the help of a debugger).


For Gcc there are "bounds checking patches". Unfortunately, they are not in the mainline source, also they only work for C and not for C++ (but they work well with mixed C and C++ programs in the C modules). It is quite a bit of work, to install and use such a bounds checking gcc (especially, when you want to use it in parallel to an unpatched gcc). I have used it under Linux. Did anybody try to apply the bounds checking patches for MinGW, Cygwin or DJGPP? Does it work under these environments. How to setup it? Are even binaries available?

Are there any other free (say as in free beer) choices available for a C compiler running under Windows or DOS (with DOS extender), that have bounds checking features. I am aware of libraries, that can check malloced memory, but they seem to miss out of bounds array accesses?

Regards,
Dieter

[Tom Likens]

I have seen in some program that limits ply, ej TSCP
if (ply > MAX_PLY - 1)
return eval();
This continues failing for my, the peculiar thing is that if I do
if (ply > MAX_PLY/2 - 1)
the thing works well.

Very strange. Is it possible that you try to access some array with MAX_PLY elements, and that your array index is accidentally incremented and decremented by 2 rather than 1 when you make and unmake moves?

At any rate, it sounds like you have an array out of bounds bug somewhere. If your C compiler supports some kind of optional bounds checking, switch it on, recompile your program, and run WAC237 again.

I just grepped for MAXPLY in my sources. Several parts depend on MAXPLY, not only the PV. At first glance I saw killer moves, move list and several internal Yace specific tables. One would also need to take care of filling the PV after a hash cutoff. I use an end marker in several arrays (like the ones used for the PV), so one has to be aware of that additional entry needed for the endmarker (and also make sure, that the endmarker is always there, which might not be the case, when just returning eval).

It should be a good idea, to always (in debug mode) check PV moves for legality. One could also plug in such code, at the time, any move is written to the PV array, not only when actually formating it for output. This way, one should be able to find the spot of the problem easier (with the help of a debugger).


For Gcc there are "bounds checking patches". Unfortunately, they are not in the mainline source, also they only work for C and not for C++ (but they work well with mixed C and C++ programs in the C modules). It is quite a bit of work, to install and use such a bounds checking gcc (especially, when you want to use it in parallel to an unpatched gcc). I have used it under Linux. Did anybody try to apply the bounds checking patches for MinGW, Cygwin or DJGPP? Does it work under these environments. How to setup it? Are even binaries available?

Are there any other free (say as in free beer) choices available for a C compiler running under Windows or DOS (with DOS extender), that have bounds checking features. I am aware of libraries, that can check malloced memory, but they seem to miss out of bounds array accesses?

Regards,
Dieter

Hello Dieter,

Unfortunately, I'm not aware of any free bounds checkers under Windows or DOS.
If you run under Linux, Valgrind is very good (in my opinion, it rivals many of the
commercial products, and it's free as in beer).

http://valgrind.org/

regards,
--tom

[Anonymous]

Tom, can you or anybody else try this program with valgrind:

Code: Select all

/* Untested, just typed into the post - I hope, I got it right */
#include <stdio.h>

void bug(int *, int * int *); /* Forword declaration, so that the compiler probably will not see the problem (when not optimizing) by source code analysis */

int main(void)
{
  int a[2], b[2], c[2];
  bug(a,b,c);
  printf("%d %d %d %d %d %d\n", a[0], a[1], b[0], b[1], c[0], c[1]);
  return 0;
}

void bug(int *a, int *b, int *c)
{
  int i;
  a[0]=a[1]=c[0]=c[1]=0;
  for (i=-2; i<4; i++)
    b[i] = i; /* out of bounds array access */
}


I thought to remember, that valgrind cannot detect such problems. Gcc with bounds checking patches detects it.

Can anybody try the code with boundschecker (?) under Windows?

Regards,
Dieter

[Dann Corbit]

Without bounds checker, I get this:
Run-Time Check Failure #2 - Stack around the variable 'c' was corrupted.

I will try a run with BoundsChecker also.

[Anonymous]

Without bounds checker, I get this:
Run-Time Check Failure #2 - Stack around the variable 'c' was corrupted.

I will try a run with BoundsChecker also.

Thanks, Dann. Seems I assumed too much. I assumed, that the stack layout will be either 8 bytes for each of a, b and c. In this order, or just in reverse order. Seems the compiler reordered this. I guess, my intention was clear. I wanted to have an out of bounds array access, that probably does not anything harmful (in the sense accessing memory, not available) at runtime. You certainly can find a similar example, that should work in the sense I mean.

The question is, will bounds checker detect out of bounds array accesses in general. The array might be local, static, static inside a function or global. Detecting simple out of bounds accesses for malloced memory is much easier by a tailored malloc() with some fence at the start and at the end. that is initialized to some magic values.

You certainly also detected my typo, where one "," is missing in the prototype for bug.

How did you compile the program (which compiler options), to detect the stack corruption?

Regards,
Dieter

[Anonymous]

I got (after adding that missing "," to the source I posted:

C:\src>cl bug.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.40607.16 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.

bug.c
Microsoft (R) Incremental Linker Version 8.00.40607.16
Copyright (C) Microsoft Corporation. All rights reserved.

/out:bug.exe
bug.obj

C:\src>bug
2 3 0 1 -2 -1

This is exactly, what I expected. With the options you used, Dann, perhaps just changing the for loop to

for (i=0; i<4; i++)

or to

for (i=-2; i<2; i++)

would be enough, to get the behaviour I intended (no stack corruption shoud be detected with one of the 2 choices).

Regards,
Dieter

[Dann Corbit]

This is interesting:
http://manju.cs.berkeley.edu/cil/

Along with the ccured, it seems to provide a bounds checking mechanism.

[Dann Corbit]

Without bounds checker, I get this:
Run-Time Check Failure #2 - Stack around the variable 'c' was corrupted.

I will try a run with BoundsChecker also.

Thanks, Dann. Seems I assumed too much. I assumed, that the stack layout will be either 8 bytes for each of a, b and c. In this order, or just in reverse order. Seems the compiler reordered this. I guess, my intention was clear. I wanted to have an out of bounds array access, that probably does not anything harmful (in the sense accessing memory, not available) at runtime. You certainly can find a similar example, that should work in the sense I mean.

The question is, will bounds checker detect out of bounds array accesses in general. The array might be local, static, static inside a function or global. Detecting simple out of bounds accesses for malloced memory is much easier by a tailored malloc() with some fence at the start and at the end. that is initialized to some magic values.

You certainly also detected my typo, where one "," is missing in the prototype for bug.

How did you compile the program (which compiler options), to detect the stack corruption?

Regards,
Dieter

/Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_MBCS" /FD /EHsc /RTC1 /MLd /YX"stdafx.h" /Fp".\Debug/foo.pch" /Fo".\Debug/" /Fd".\Debug/" /W3 /nologo /c /ZI /TP

[Tom Likens]

Tom, can you or anybody else try this program with valgrind:

Code: Select all

/* Untested, just typed into the post - I hope, I got it right */
#include <stdio.h>

void bug(int *, int * int *); /* Forword declaration, so that the compiler probably will not see the problem (when not optimizing) by source code analysis */

int main(void)
{
  int a[2], b[2], c[2];
  bug(a,b,c);
  printf("%d %d %d %d %d %d\n", a[0], a[1], b[0], b[1], c[0], c[1]);
  return 0;
}

void bug(int *a, int *b, int *c)
{
  int i;
  a[0]=a[1]=c[0]=c[1]=0;
  for (i=-2; i<4; i++)
    b[i] = i; /* out of bounds array access */
}


I thought to remember, that valgrind cannot detect such problems. Gcc with bounds checking patches detects it.

Can anybody try the code with boundschecker (?) under Windows?

Regards,
Dieter

Dieter,

You're correct Valgrind as good as it is doesn't handle this type of error. It only finds leaks
if the memory was allocated dynamically. I ran your code under BoundsChecker and it
found the error giving the following message:

Pointer Error: The pointer 0x12FF68 is no longer within buffer 0x12FF70 (8), variable b in function main.

It also gives you the option of debugging it immediately by highlighting the offending line
and jumping into the debugger. Of course, the downside is that it is expensive to buy if you
aren't a professional programmer with an unlimited budget.

regards,
--tom

[Anonymous]

Tom, so bounds checker will reliably find out of bounds array accesses (when the arrays are not malloced)? I assume you checked for the thing, that happened on Dann's computer, where probably the memory layout of a,b,c was reorderd. When b is not in the middle, it might be easier to find the problem.

Any idea, how bounds checker works? As I understand, it is an addon to MSVC. Does it change code generation? I have a hard time, to see how a pure addon can detect these things ... Valgrind "works" as expected in this case. It does not do anything to the code generation.

b[2] = 0;

may produce some code like

mov 0 to offset 8 after the adress pointed to by b

If this is a valid adress, how should an addon detect, that the adress does not belong to object b?

Does bounds checker detect simple:

Code: Select all

/* module a */

int a[2]; /* In one module, more global vars before and after a in the actual memory layout */

/* module b */

extern int a[];

void foo(void)
{
  a[2] = 0;
}


Regards,
Dieter

[Tom Likens]

Tom, so bounds checker will reliably find out of bounds array accesses (when the arrays are not malloced)? I assume you checked for the thing, that happened on Dann's computer, where probably the memory layout of a,b,c was reorderd. When b is not in the middle, it might be easier to find the problem.

Any idea, how bounds checker works? As I understand, it is an addon to MSVC. Does it change code generation? I have a hard time, to see how a pure addon can detect these things ... Valgrind "works" as expected in this case. It does not do anything to the code generation.

b[2] = 0;

may produce some code like

mov 0 to offset 8 after the adress pointed to by b

If this is a valid adress, how should an addon detect, that the adress does not belong to object b?

Does bounds checker detect simple:

Code: Select all

/* module a */

int a[2]; /* In one module, more global vars before and after a in the actual memory layout */


/* module b */

extern int a[];

void foo(void)
{
  a[2] = 0;
}


Regards,
Dieter

Hey Dieter,

Unfortunately, I don't have access to my Windows machine at the moment. I will have access
tomorrow, so I'll run your new code snippet through BoundsChecker then and post the
results afterwards.

As for how BoundsChecker works, it does integrates into the Visual Studio environment, but
it uses a technique called "Compile-Time Instrumentation" (CTI). BC actually adds a
preprocessing step to the compilation process that adds a number of run-time checking
functions to the program whenever the code does any of the following:

* (Re)Allocates or releases memory
* Assigns a value to a pointer
* Reads a pointer's value
* References an array
* Calls or returns from a function

This behind-the-scenes code performs all the "magic" of actually catching the illegal
accesses. For large programs I've found the instrumented code runs *very* slowly. You can
decrease the level of error checking to speed things up, but of course you then start to
lose the main benefit of the program.

The following (competitor's) website gives an interesting overview of BoundsChecker 4.0
(admittedly an "ancient" version, but still interesting and likely relevant).

http://www.microquill.com/heapagent/ha_comp.htm

regards,
--tom

[Anonymous]

Hi Tom,

thanks for your interesting answer and for the link. While the discussion was until now rather on topic IMHO (a concrete bug situation from Pedro, and discussion about tools, that can help in such a situation - a situation that may be typical for many chess engine), we are drifting away by my technical questions. So, perhaps you might prefer to answer the real technical stuff to my email at buers@gmx.de.

I wonder, does assembly output still work with bounds checker instrumented code? If yes, can you send the assembly output of the instrumented code of my first example? Does bounds checker also work with command line compiles? (I looked at the official site, and could not find much information about this)
I also wonder, how bounds checker can plug in this preprocessing step into a foreign compiler. Do the MS compiling environments have any API (documented), that such a tool can use?

With the bounds checking patches to Gcc, it is easy to understand to me. The compiler sources are patched directly, and some new functionality is added. The patches will change the code generation (adding checking code to any array access, for example).

Regards,
Dieter

[mridul]

Hi Dieter,

When I used it long ago , actually what I thought it did was one of the following :

1) have guard blocks of arrays between the stack arrays - dont think it is done like this.
2) Instead of allocating on stack , it will dynamically allocate them and then assigns them as pointers through instrumentation.

I think 2 is more plausible since the nomal hacks to find the direction of how stack grows ((unsigned)arr1 - (unsigned)arr2) seems to fail to reliably give an answer across runs .... or maybe I was observing some noise/bugs in my own code , both equally likely

Anyway , instrumentation is a very interesting field ... have looked a bit at JFluid a while ago and was blown away by the complexity of the software/ideas as such and the power it can weild.

Mridul