Subject: [Sip] Is body handling NP-complete?

From: [email-masked]
Date: Mon, 29 Sep 2008 23:09:58 -0400 (EDT)

Referring back to last March, in
http://www.ietf.org/mail-archive/web/sip/current/msg22426.html, I was
contemplating whether the rules for testing a message body required
searching through combinations of choices regarding which alternatives
of multipart/alternatives are chosen.  As I then conceptualized the
problem, the question was "Is there a choice of alternatives such that
all the constraints for 'successful processing' can be met?"  It turns
out that if you phrase the question that way, the problem is
NP-complete, which means in practice that any algorithm to solve it
must do backtracking.

The new formulation of the problem attempts to avoid this by dividing
the problem into three phases:  (1) assemble a tree which represents
the dependencies of super-parts' being processable upon that of
sub-parts, (2) walk the tree, tagging parts from the bottom up as to
whether they are processable, (3) if the overall tree is processable,
selecting for processing the correct subset of parts as directed by
the tags in the tree.  As long as the size of the tree is commensurate
with the number of body parts, the algorithm is inherently linear, and
clearly it doesn't involve backtracking.

In regard to step (1), the tree is assembled:

- the root node represents the message body
- a node for a multipart/alternative part has one child for each
  component
- a node for a multipart/mixed part has one child for each
  component
- a note for a multipart/related part is not automatically given
  children for its components
- a header in a part that refers to another component generates a
  child of that part that represents the referred-to component
- similarly, a reference within a part that refers to another
  component generates a child of that part that represents the
  referred-to component (This is how multipart/related nodes get
  children.)

Of course, if a component is referred to multiple times, the component
is represented by multiple nodes in the tree, one node for each of its
roles.

However, there are subtleties I might be overlooking, so I am going to
revisit the embedding of the NP-complete problem "3-satisfiability"
into MIME to see what it reveals about my sketch of an algorithm.

Referring to the previous message:

    The reduction is as follows:

    http://en.wikipedia.org/wiki/NP-complete
    http://en.wikipedia.org/wiki/Reduction_%28complexity%29
    http://en.wikipedia.org/wiki/3-satisfiability#3-satisfiability

    Choose an instance of the 3-satisfiability problem, that is: a set of
    boolean variables A, B, C, etc. and a formula composed of:
	    a series of "clauses" joined by AND, consisting of
		    a series of variables and their negations joined by OR.
    The problem is to determine if there is any assignment of truth values
    to the variables which makes the formula true, that is, which makes
    true one of the variables or negations in each of the clauses.

    For example, choose 4 variables A, B, C, and D, and the formula

    (A OR B OR C) AND (B OR NOT-C OR D) AND (NOT-A OR NOT-B OR NOT-D)

    This can be satisfied by setting A=TRUE, B=FALSE, C=TRUE, and D=FALSE.

    Construct a multipart/mixed with each component labeled
    handling=required.  Within that, for each variable, have a part which
    is multipart/alternate with 2 parts.  If processing chooses the first
    part of the part corresponding to a variable, that will model the
    variable being TRUE.  If processing chooses the second part of the
    part corresponding to a variable, that will model the variable being
    FALSE.

    For example, our body starts:

	    multipart/mixed
		    multipart/alternative;handling=required
			    first part corresponding to A (not yet specified)
			    second part corresponding to NOT-A
		    multipart/alternative;handling=required
			    first part corresponding to B
			    second part corresponding to NOT-B
		    multipart/alternative;handling=required
			    first part corresponding to C
			    second part corresponding to NOT-C
		    multipart/alternative;handling=required
			    first part corresponding to D
			    second part corresponding to NOT-D

    For each clause of the formula, add an additional body part, marked
    "Content-Disposition: by-reference; handling=required".  Give the part
    a 'cid' URL.  The ability of the recipient to successfully process
    this part will model making the corresponding clause TRUE.

    For example, our body is now:

	    multipart/mixed
		    multipart/alternative;handling=required
			    first part corresponding to A (not yet specified)
			    second part corresponding to NOT-A
		    multipart/alternative;handling=required
			    first part corresponding to B
			    second part corresponding to NOT-B
		    multipart/alternative;handling=required
			    first part corresponding to C
			    second part corresponding to NOT-C
		    multipart/alternative;handling=required
			    first part corresponding to D
			    second part corresponding to NOT-D
		    part (not otherwise specified);by-reference;handling=required;cid=clause1
		    part (not otherwise specified);by-reference;handling=required;cid=clause2
		    part (not otherwise specified);by-reference;handling=required;cid=clause3

    We now want to arrange things so that one of the last 3 parts can be
    successfully processed only if we choose for processing one of the
    earlier parts that corresponds to a variable value that will make the
    corresponding clause true.  This is done by embedding forward
    references in the variable-corresponding parts that refer to the
    clause-corresponding parts.

    For example:

 1	    multipart/mixed
 2		    multipart/alternative;handling=required
 3			    first part corresponding to A
				    references cid:clause1
 4			    second part corresponding to NOT-A
				    references cid:clause3
 5		    multipart/alternative;handling=required
 6			    first part corresponding to B
				    references cid:clause1
				    references cid:clause2
 7			    second part corresponding to NOT-B
				    references cid:clause3
 8		    multipart/alternative;handling=required
 9			    first part corresponding to C
				    references cid:clause1
10			    second part corresponding to NOT-C
				    references cid:clause2
11		    multipart/alternative;handling=required
12			    first part corresponding to D
				    references cid:clause2
13			    second part corresponding to NOT-D
				    references cid:clause3
14		    part;by-reference;handling=required;cid=clause1
15		    part;by-reference;handling=required;cid=clause2
16		    part;by-reference;handling=required;cid=clause3

    In order to process this body, the recipient must choose exactly one
    of each pair of bodies in the multipart/alternative body parts.  This
    choice is equivalent to choosing a set of values for the variables.
    The references embedded in the chosen parts refer to the body parts
    that correspond to the clauses which are made true by the
    corresponding variable's value.  In order to successfully process the
    final body parts, the recipient must have chosen a set of variable
    values that makes all of the clauses true.

The resulting tree is:

	1 -+- 2 --+- 3 ---- 14
	   |      |
	   |      +- 4 ---- 16
	   |
	   +- 5 --+- 6 --+- 14
	   |      |      |
	   |      |      +- 15
	   |      |
	   |      +- 7 ---- 16
	   |
	   +- 8 --+- 9 ---- 14
	   |      |
	   |      +- 10 --- 15
	   |
	   +- 11 -+- 12 --- 15
	   |      |
	   |      +- 13 --- 16
	   |
	   +- 14
	   |
	   +- 15
	   |
	   +- 16

Though the number of nodes is greater than the number of body parts,
it's limited approximately by the number of appearances of variables
in the original boolean formula, so it's linear in the number of body
parts.  So in building the tree, we don't have exponential effort.

In the new approach, we walk the tree, tagging each node as to whether
it is processable.  In the above model, we assume that all the simple
parts are processable, so all nodes labeled 2 through 16 are marked
processable.  And as we tag the nodes for processability, we choose
for each multipart/alternative node which child will be processed
(namely, the last child that is processable).  In this tree, the
choices are 2 -> 4, 5 -> 7, 8 -> 10, and 11 -> 13.

Where things get interesting is deciding if node 1 is processable.
All of its children are processable, of course.  But the crux of the
construction is how the "by-reference;handling=required" constraints
on nodes 14, 15, and 16 are handled.  In this algorithm, we check
whether each part is referenced by a part that will be processed.
Fortunately, all references to these nodes must have been tree-walked
before node 1 is examined, so can determine unambiguously whether used
references point to those nodes.  In this case, we have chosen to
process 2, 4, 5, 7, 8, 10, 11, and 13, which means that there are used
references to 16, 16, 15, and 16.  This leaves 17 unreferenced, and so
node 1 is determined to be unprocessable.

Note that the new algorithm avoids being NP-complete essentially by
making choices as soon as they are seen.  In this model, values NOT-A,
NOT-B, NOT-C, and NOT-D are chosen outright.  Since the example
formula is not satisfied, the body that encodes it is not processable.

This example also points out that the requirement that references
appear before the parts they reference is needed to make the problem
tractable.  Otherwise, there could be circular dependencies between
the choices for different multipart/alternatives, which might be
impossible to analyze by an algorithm as simple as a tree-walk.

Dale
_______________________________________________
Sip mailing list  https://www.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: Paul Kyzivat <[email-masked]>
Date: Tue, 30 Sep 2008 09:52:50 -0400

Dale,

I like the thorough treatment. It seems plausible to me.

One implication of this is that body parts need to be processed twice in 
a content-type+content-disposition+context dependent way: once to 
extract references, and again for final effect. (Hmm - is extracting of 
references dependent on the disposition and context?)

If you imagine that various content types are handled by plugins, then 
the plugins will each require two entry points - one for each of these 
processing modes. While that is certainly possible, it might mean that 
plugins that already exist for non-sip applications (e.g. email or html) 
may not be reusable for sip. (I am not familiar with the content-type 
plugins for other protocols such as email. But I presume that email 
plugins may be useful in some cases, at least for MESSAGE.)

Do plugins for email have this complexity?

An alternative is to do all the processing in one pass, and then at the 
end check if all body parts have been processed. BUT that means all the 
side effects of processing will have been realized before discovering 
that the message is in error. That is certainly not ideal.

> impossible to analyze by an algorithm as simple as a tree-walk.

This requirement is satisfied by lots of simple cases. But it means that 
it is impossible to describe any kind of circular structure. I'm not 
familiar enough with the use of multipart/related to know if it is a 
restriction that is tolerable there. Perhaps someone can comment on that.

	Thanks,
	Paul

---

From: "DRAGE, Keith \(Keith\)" <[email-masked]>
Date: Wed, 1 Oct 2008 00:18:07 +0200

I would note that if this does end up in the specification, it can carry
a rider that implementations should exhibit behaviour as demonstrated by
the algorithm, not that they need to implement the algorithm itself. 

However I leave it to the working group to ascertain whether they prefer
this as a means of specification.

Regards

Keith

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Paul Kyzivat
> Sent: Tuesday, September 30, 2008 2:53 PM
> To: [email-masked]
> Cc: [email-masked]
> Subject: Re: [Sip] Is body handling NP-complete?
> 
> Dale,
> 
> One implication of this is that body parts need to be 
> processed twice in a content-type+content-disposition+context 
> dependent way: once to extract references, and again for 
> final effect. (Hmm - is extracting of references dependent on 
> the disposition and context?)
> 
> If you imagine that various content types are handled by 
> plugins, then the plugins will each require two entry points 
> - one for each of these processing modes. While that is 
> certainly possible, it might mean that plugins that already 
> exist for non-sip applications (e.g. email or html) may not 
> be reusable for sip. (I am not familiar with the content-type 
> plugins for other protocols such as email. But I presume that 
> email plugins may be useful in some cases, at least for MESSAGE.)
> 
> An alternative is to do all the processing in one pass, and 
> then at the end check if all body parts have been processed. 
> BUT that means all the side effects of processing will have 
> been realized before discovering that the message is in 
> error. That is certainly not ideal.
> 
> This requirement is satisfied by lots of simple cases. But it 
> means that it is impossible to describe any kind of circular 
> structure. I'm not familiar enough with the use of 
> multipart/related to know if it is a restriction that is 
> tolerable there. Perhaps someone can comment on that.
> 
> 	Thanks,
> 	Paul
> 
> > 		    part (not otherwise 
> specified);by-reference;handling=required;cid=clause1
> > 		    part (not otherwise 
> specified);by-reference;handling=required;cid=clause2
> > 		    part (not otherwise 
> > specified);by-reference;handling=required;cid=clause3
> > 
> > This list is for NEW development of the core SIP Protocol Use 
> > [email-masked] for questions on current sip Use 
> > [email-masked] for new developments on the application of sip
> > 
> This list is for NEW development of the core SIP Protocol Use 
> [email-masked] for questions on current sip