From: rickert@mp.cs.niu.edu (Neil Rickert)
Newsgroups: comp.mail.sendmail
Subject: Re: Dbm lookup bug in sendmail-5.65c+IDA-1.4.4.1 (with patch)
Keywords: sendmail bug dbm ida patch
Date: 8 Apr 92 18:43:45 GMT
Organization: Northern Illinois University

In article <1992Apr8.150755.13793@ohm.york.ac.uk> nigelm@ohm.york.ac.uk (Nigel Metheringham) writes:
>I have discovered a fairly serious bug in the handling of dbm map
>matching in sendmail-5.65c+IDA-1.4.4.1.

  This is a known problem which will be corrected in the next release.
Note that 'Sendmail.mc' distributed with 1.4.4.1 does not trigger this
bug.

>A quick description of the bug is that although the basic pattern
>matching code was included in the rewrite code to handle dbm map
>matches (ie a $% in the LHS of a rule), there was no code added into
>the backup part of rewrite, so if the pattern match initially fails,
>the matcher is unable to backtrack and try again.
>
>The way this bug shows up is shown by the following rule from my
>config file:-
>  R$+@$+$%G	$@<$1@$2$3>$2$3.ether
>
>In this case the dbm map G contains a list of top level domains that
>we can use SMTP to - things like edu com se lu
>
>We found that putting the address "fred@xx.lu.se" to this rule gave
>a match on the lu part of the address to the detriment of the
>trailing se part of the address, so the rule returned
>"<fred@xx.lu>xx.lu.ether" instead of the correct
>"<fred@xx.lu.se>xx.lu.se.ether".

  Are you sure that the rule didn't just fail to match completely?  The
behavior you describe is not consistent with my experience.  I found it
sometimes failing to match when it should, but I never found it "matching"
improperly.

>Is it really the case that no one is using DBM lookups within
>sendmail - I can't imagine how this could have stayed underground
>for any length of time if the code is actually being used!

  Very few people are using it.  Most IDA users are using the distributed
'Sendmail.mc' to build their rules, and it does not use this feature.  I
did test the feature, and for a short time there was a version which could
obtained by ftp from mp.cs.niu.edu.  As soon as I discovered the problem
I eliminated use of $%x, and worked on a redesign of rewrite() in
parseaddr.c.

  Let me mention another problem with $%x, which is also alleviated in the
redesign:

  Consider your rule:

	R$+@$+$%G	$@<$1@$2$3>$2$3.ether

  Now imagine that the address is mine, 'rickert@mp.cs.niu.edu'.  Assume
that your database contains 'edu'.

  The database will be searched for the following strings:

	.
	.cs
	.cs.
	.cs.niu
	.cs.niu.
	.cs.niu.edu
	cs
	cs.
	cs.niu
	cs.niu.
	cs.niu.edu
	.
	.niu
	.niu.
	.niu.edu
	niu
	niu.
	niu.edu
	.
	.edu
	edu

and will finally match on the last.  Since each of these lookups will
very likely involve both a read() of a record from the dbm file, and
a seqential search through the block read, the could potentially be a
serious performance hit.  This could be particularly serious with some of
the long domain names in use.  Class matches already involved this sequence
of lookups, but since they are all done in memory the cost is somewhat
less serious.  (It is probably out of concern for this type of performance
problem that Berkeley has not gone to multi-token matches).

 With my redesign of rewrite() the lookups in the above would be reduced to

	.cs.niu.edu
	cs.niu.edu
	.niu.edu
	niu.edu
	.edu
	edu

 Essentially before $%x (similarly for $=x) is matched, a check is made
to see if the next token on the LHS is an ordinary character token,
and if so that is matched first.  With your example, the next token is the
end marker, so the $%x match would only be attempted on strings terminating
at the end of the address.

-- 
=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
  Neil W. Rickert, Computer Science               <rickert@cs.niu.edu>
  Northern Illinois Univ.
  DeKalb, IL 60115                                   +1-815-753-6940
Newsgroups: comp.mail.multi-media,comp.mail.misc