#24 6.4.2 A constraint after a multifield wildcard read outside the slot

[Batch Job 1]

What happened. A return value constraint in the field after a multifield wildcard read memory outside the slot, and gave an answer that came from whatever was there.

(deftemplate JO (slot id) (multislot members))
(defrule crash (JO (id ?id) (members $? =(sym-cat ?id))) =>)
(assert (JO (id gen1) (members gen1)))

Under AddressSanitizer that is a heap-buffer-overflow read at factrete.c in FactPNGetVar1. The same rule across two patterns reports in FactJNGetVar1, and over instances in GetObjectValueGeneral in objrtfnx.c. It is reachable from the CLIPS 7.0.0 test suite, where drtest11.tst ends in a segmentation fault on 6.4.2.

The answers were wrong as well as undefined. The constraint was tested against a fixed field position whatever the slot held, so it was right only for a slot of exactly the width the pattern happened to assume.

Why it is a fix and not a preference. Section 5.4.4 documents a multifield wildcard inside a slot pattern, and section 5.4.6.6 documents = as a return value constraint usable where a constraint is usable. Both are what the manual documents, and reading outside an allocated block is not a behaviour any reading of it permits.

Where it came from. The constraint was fetched by the wrong one of three accessors.

CLIPS has three routines for reading a field during pattern matching, chosen in FactGenGetfield and FactReplaceGetfield in clips_core_source_642/core/factgen.c, with join network counterparts in FactGenGetvar and FactReplaceGetvar:

• FactPNGetVar2 for a single field slot, which needs only the slot number;
• FactPNGetVar3 for a field in a multifield slot with at most one wildcard before it, which reads the position relative to the slot's own length;
• FactPNGetVar1 for everything else, which reads the position from the multifield markers built during matching.

A wildcard inside a slot is not compiled to a pattern node of its own — CreateNewPatternNode in factbld.c marks a node multifieldNode only for MF_WILDCARD_NODE and MF_VARIABLE_NODE, and the two nodes built for (members $? =(sym-cat ?id)) are both single field nodes, one carrying leaveFields of 1. So ProcessMultifieldNode never runs for this pattern and no marker is ever created. AdjustFieldPosition with no marker returns the field number unchanged:

   actualIndex = whichField;
   for (; markList != NULL; markList = markList->next)
     { … actualIndex = actualIndex + markList->range - 1; }

which is why the first accessor cannot answer this and the third can. The third was not chosen because its condition lists the node types that occupy one field and a return value constraint is not among them:

   if (((theNode->pnType == SF_WILDCARD_NODE) || (theNode->pnType == SF_VARIABLE_NODE) || ConstantNode(theNode)) &&
       ((theNode->multiFieldsBefore == 0) ||
        ((theNode->multiFieldsBefore == 1) && (theNode->multiFieldsAfter == 0))))

The node for =(sym-cat ?id) is a RETURN_VALUE_CONSTRAINT_NODE, and it arrives with multiFieldsBefore of 1 and multiFieldsAfter of 0 — which satisfies the second half of that condition exactly. Only its type kept it out, so it fell through to FactGetVarPN1 and the markers that are not there.

A literal or a plain variable in the same position was always right, because both are in the list.

The change. One clause, || (theNode->pnType == RETURN_VALUE_CONSTRAINT_NODE), at each of the seven places that make the choice. Six are in factgen.c — FactGenGetfield and FactReplaceGetfield for the pattern network, FactGenGetvar and FactReplaceGetvar for the join network, and FactGetVarPN3 and FactGetVarJN3, which pick fromBeginning or fromEnd once the routine has been chosen. The seventh is GenObjectGetVar in objrtgen.c, the object network's counterpart, which has the same fromBeginning and fromEnd structure.

Four of the seven do not test ConstantNode and three do. That difference is left exactly as it stood. Making all seven alike was tried first and backed out: it moves where a constant in a multifield slot is read from, which is a second change with its own consequences and nothing measured behind it. The text added to each site is identical, which is what lets the whole of this be taken out again in one edit.

FactGetVarPN3 then does the arithmetic it was written for:

      else
        {
         hack.fromBeginning = 0;
         hack.fromEnd = 1;
         hack.beginOffset = 0;
         hack.endOffset = theNode->singleFieldsAfter;
        }

and FactPNGetVar3 reads

     { fieldPtr = &segmentPtr->contents[segmentPtr->length - (hack->endOffset + 1)]; }

The position is counted back from the slot's length, so it follows the wildcard at any width. Nothing was added: the mechanism was already there, and the node was being sent past it.

factrete.c and objrtfnx.c are byte-identical to the sources as shipped. The fix is 61 differing lines in factgen.c and 9 in objrtgen.c, most of them comment.

What was checked. tests/wildcard-then-constraint.clp gives output identical to CLIPS 7.0.0, line for line, across the constraint after the wildcard in all three networks — the fact pattern network, the fact join network and the object network — against slots of nought, one, two and three fields; the literal and plain-variable spellings of the same position, which have to keep matching at every width; and the constraint written before the wildcard.

AddressSanitizer is the instrument here, not the exit status. ../a pattern's own fact address was read as a slot number fixes the other defect in this area, and with it in place the read outside the slot no longer reaches an unmapped page: a build with these seven clauses removed runs to the end and answers wrongly rather than stopping.

So run-fix-tests.sh builds the core twice under -fsanitize=address with -DMEM_TABLE_SIZE=0, CLIPS's own debug allocator, without which every free goes onto a free list inside CLIPS and nothing is seen. The build as it stands reports nothing; the build with the clauses removed reports heap-buffer-overflow, and its one-field slot stops matching.

The whole of ../../v1/fact-functions/tests gives identical output, and every other suite under ../ and ../../clips-optimizations/ passes.

In the CLIPS 7.0.0 suite, drtest11.tst no longer ends in a segmentation fault. With ../a pattern's own fact address was read as a slot number, which fixes the other crash in that file, it runs to completion: its dribble output had been cut off at exactly 8192 bytes, one buffer.

Fixed upstream, and this is not upstream's fix. CLIPS 7.0.0 is clean here and gives these answers. Its own version of this code is a redesign — factbld.c differs by 886 lines and factgen.c by 468, and ProcessMultifieldNode gains a CLIPSBitMap * and a bool. Those lines are three features its file header names: data driven backward chaining, deftemplate inheritance, and non-reactive fact patterns. factrete.c's accessors and factbld.c's multifieldNode test are identical between the two versions, so the mechanism this fix uses is the one 6.4.2 already had.