1. A computer-implemented method of determining whether to merge two symbolic analysis states, wherein a first state corresponds to a first set of paths through a target program to a target program location, and a second state corresponds to a second set of paths through the target program to the target program location, the first set of paths differing from the second set of paths, the method comprising:
determining a set of one or more variables of the target program at the target program location;
analyzing values of each variable in the set to determine an impact of merging the first state and the second state, the analyzing comprising, for each variable in the set:
determining a first value of the variable in the first state, wherein the first value is either a first concrete value or a symbolic value;
determining a second value of the variable in the second state, wherein the second value is either a second concrete value or a symbolic value; and
determining, based on the first value and the second value, whether merging the first state and the second state would be advantageous with regard to the variable,
determining whether merging the first state and the second state would be advantageous comprising at least one of:
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable;
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable based on a comparison of the first value and the second value;
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being identical, determining that merging the first state and the second state would be advantageous with regard to the variable; and
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being different, determining that merging the first state and the second state would not be advantageous with regard to the variable;
determining, based on the analyzing of the values of each variable in the set, that, on balance, merging the first state and the second state will yield a net benefit, the net benefit comprising an overall reduction in time required to analyze the target program or an increase in a total number of program behaviors explored in a given time; and
responsive to determining that merging the first and second states will yield a net benefit, determining to merge the first state and the second state to produce a merged state, the merged state including all information corresponding to the first and second sets of paths that was included in the first and second states.
2. The computer-implemented method of claim 1, further comprising, responsive to determining that merging the first state and the second state would not be advantageous for all variables in the set, determining not to merge the first state and the second state.
3. The computer-implemented method of claim 1, wherein a variable in the set is likely to cause many queries to a constraint solver if that variable were to contain a symbolic value.
4. The computer-implemented method of claim 1, wherein determining the set of one or more variables comprises determining how many times a variable will appear in a constraint solver query that occurs after the target program location.
5. The computer-implemented method of claim 1, wherein determining the set of one or more variables comprises estimating how often a variable is used in a branch condition that occurs after the target program location.
6. A computer-implemented method of selecting a symbolic analysis state from a general worklist when analyzing a target program, the method comprising:
predicting, based on a reached-state history, whether one or more states in the general worklist will be mergeable with another state in the general worklist after at most a predetermined number of steps of execution to yield a net benefit, the net benefit comprising an overall reduction in time required to analyze the target program or an increase in a total number of program behaviors explored in a given time;
responsive to predicting that one or more states will be mergeable with another state after at most the predetermined number of steps of execution to yield a net benefit, selecting a first state from among the one or more states;
responsive to predicting that no states in the general worklist will be mergeable after at most the predetermined number of steps of execution to yield a net benefit, selecting a state from the general worklist according to a heuristic; and
determining whether merging the first state with a second state that is a predecessor state or a successor state of the corresponding another state would be advantageous, the determining comprising:
analyzing values of each variable in a set of one or more variables of the target program to determine an impact of merging the first state and the second state, the analyzing comprising, for each variable in the set:
determining a first value of the variable in the first state, wherein the first value is either a first concrete value or a symbolic value;
determining a second value of the variable in the second state, wherein the second value is either a second concrete value or a symbolic value; and
determining, based on the first value and the second value, whether merging the first state and the second state would be advantageous with regard to the variable, determining whether merging the first state and the second state would be advantageous comprising at least one of:
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable;
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable based on a comparison of the first value and the second value;
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being identical, determining that merging the first state and the second state would be advantageous with regard to the variable; and
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being different, determining that merging the first state and the second state would not be advantageous with regard to the variable;
determining, based on the analyzing of the values of each variable in the set, that, on balance, merging the first state and the second state will yield a net benefit, the net benefit comprising an overall reduction in time required to analyze the target program or an increase in a total number of program behaviors explored in a given time; and
responsive to determining that merging the first and second states will yield a net benefit, determining to merge the first state and the second state to produce a merged state, the merged state including all information corresponding to the first and second sets of paths that was included in the first and second states.
7. The computer-implemented method of claim 6, further comprising executing the selected state.
8. The computer-implemented method of claim 6, wherein the selected state corresponds to a first target program location, and the corresponding another state corresponds to a second target program location, and wherein the first target program location and the second target program location are different.
9. The computer-implemented method of claim 8, wherein predicting that the selected state will be mergeable with the corresponding another state after at most the predetermined number of steps of execution to yield a net benefit comprises:
determining that a successor state of the selected state will reach the second target program location within at most the predetermined number of steps of execution.
10. The computer-implemented method of claim 6, wherein the heuristic comprises a random search heuristic.
11. The computer-implemented method of claim 6, wherein the heuristic comprises a coverage-oriented search heuristic.
12. A non-transitory computer-readable storage medium storing executable computer program instructions for determining whether to merge two symbolic analysis states, wherein a first state corresponds to a first set of paths through a target program to a target program location, and a second state corresponds to a second set of paths through the target program to the target program location, the first set of paths differing from the second set of paths, the instructions performing steps comprising:
determining a set of one or more variables of the target program at the target program location;
analyzing values of each variable in the set to determine an impact of merging the first state and the second state, the analyzing comprising, for each variable in the set: determining a first value of the variable in the first state, wherein the first value is either a first concrete value or a symbolic value;
determining a second value of the variable in the second state, wherein the second value is either a second concrete value or a symbolic value; and
determining, based on the first value and the second value, whether merging the first state and the second state would be advantageous with regard to the variable,
determining whether merging the first state and the second state would be advantageous comprising at least one of:
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable;
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable based on a comparison of the first value and the second value;
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being identical, determining that merging the first state and the second state would be advantageous with regard to the variable; and
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being different, determining that merging the first state and the second state would not be advantageous with regard to the variable;
determining, based on the analyzing of the values of each variable in the set, that, on balance, merging the first state and the second state will yield a net benefit, the net benefit comprising an overall reduction in time required to analyze the target program or an increase in a total number of program behaviors explored in a given time; and
responsive to determining that merging the first and second states will yield a net benefit, determining to merge the first state and the second state to produce a merged state, the merged state including all information corresponding to the first and second sets of paths that was included in the first and second states.
13. A computer system for determining whether to merge two symbolic analysis states, wherein a first state corresponds to a first set of paths through a target program to a target program location, and a second state corresponds to a second set of paths through the target program to the target program location, the first set of paths differing from the second set of paths, the computer system comprising:
at least one non-transitory computer-readable storage medium storing executable computer program instructions comprising instructions for:
determining a set of one or more variables of the target program at the target program location;
analyzing values of each variable in the set to determine an impact of merging the first state and the second state, the analyzing comprising, for each variable in the set:
determining a first value of the variable in the first state, wherein the first value is either a first concrete value or a symbolic value;
determining a second value of the variable in the second state, wherein the second value is either a second concrete value or a symbolic value; and
determining, based on the first value and the second value, whether merging the first state and the second state would be advantageous with regard to the variable, determining whether merging the first state and the second state would be advantageous comprising at least one of:
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable;
responsive to the first value being a symbolic value or the second value being a symbolic value, determining that merging the first state and the second state would be advantageous with regard to the variable based on a comparison of the first value and the second value;
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being identical, determining that merging the first state and the second state would be advantageous with regard to the variable; and
responsive to the first value being a first concrete value and responsive to the second value being a second concrete value and responsive to the first concrete value and second concrete value being different, determining that merging the first state and the second state would not be advantageous with regard to the variable,
determining, based on the analyzing of the values of each variable in the set, that, on balance, merging the first state and the second state will yield a net benefit, the net benefit comprising an overall reduction in time required to analyze the target program or an increase in a total number of program behaviors explored in a given time; and
responsive to determining that merging the first and second states will yield a net benefit, determining to merge the first state and the second state to produce a merged state, the merged state including all information corresponding to the first and second sets of paths that was included in the first and second states; and
a processor for executing the computer program instructions.
14. The computer-implemented method of claim 1, wherein the first state and the second state are merged only if the analyzing determines that merging is advantageous for all variables in the set.
15. The non-transitory computer-readable storage medium of claim 12, wherein the first state and the second state are merged only if the analyzing determines that merging is advantageous for all variables in the set.
16. The computer system of claim 13, wherein the first state and the second state are merged only if the analyzing determines that merging is advantageous for all variables in the set.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A distal end cap for an endoscope which is removably attached in an axial direction to an insertion end portion of an insertion portion disposed in the endoscope, the distal end cap comprising:
a cap proximal end portion which is disposed at a proximal end side of the distal end cap in the axial direction and attached to the insertion end portion;
a cap distal end portion which is disposed at a distal end side of the distal end cap in the axial direction, and is disposed at a position so that the cap distal end portion protrudes from an distal end surface of the insertion end portion when the cap proximal end portion is attached to the insertion end portion;
a concave portion which is disposed on the cap distal end portion from the distal end side toward the proximal end side in the axial direction;
a low-strength portion which is disposed on a same line as the concave portion in the axial direction and continuously disposed between the cap distal end portion and the cap proximal end portion in the axial direction; and
at least one high-strength portion having strength higher than that of the low-strength portion, the high-strength portion being disposed on at least a portion excluding the concave portion in an axis circumferential direction of an axis, and continuously disposed from the cap distal end portion to the cap proximal end portion in the axial direction.
2. The distal end cap for an endoscope according to claim 1, wherein a plurality of high-strength portions disposed in the axis circumferential direction.
3. The distal end cap for an endoscope according to claim 1, wherein a width of the high-strength portion in the axis circumferential direction is even from the cap distal end portion to the cap proximal end portion in the axial direction, or gradually decreases from the cap distal end portion to the cap proximal end portion in the axial direction.
4. The distal end cap for an endoscope according to claim 1, wherein the high-strength portion is disposed on the entire circumference of the cap distal end portion in the axis circumferential direction so as to include the concave portion.
5. The distal end cap for an endoscope according to claim 1, wherein
the low-strength portion includes a thin wall portion, and
the high-strength portion includes a thick wall portion.
6. The distal end cap for an endoscope according to claim 1, wherein the high-strength portion includes a reinforcing member which is different from the distal end cap to reinforce strength of at least one of an inner circumferential surface and an outer circumferential surface of the distal end cap for an endoscope.
7. The distal end cap for an endoscope according to claim 6, wherein the reinforcing member has a pillar shape with a substantially arc cross-shaped cross-section and is disposed so as to abut on the inner circumferential surface or the outer circumferential surface.
8. The distal end cap for an endoscope according to claim 6, wherein
the reinforcing member disposed on the inner circumferential surface and having a tubular shape,
the high-strength portion includes a sandwiched member which is sandwiched between the inner circumferential surface and the reinforcing member.
9. The distal end cap for an endoscope according to claim 1, wherein
the high-strength portion is formed of a material different from the low-strength portion and harder than that of the low-strength portion, and
the low-strength portion and the high-strength portion are integrally molded to one another, or molded by insert molding.
10. The distal end cap for an endoscope according to claim 1, wherein the high-strength portion is disposed so as to be adjacent to an observation unit disposed on the insertion end portion in a radial direction of the distal end cap for an endoscope when the distal end cap for an endoscope is attached to the insertion end portion.
11. The distal end cap for an endoscope according to claim 1, wherein the concave portion is disposed so as to be adjacent to an observation unit disposed on the insertion end portion in a radial direction of the distal end cap for an endoscope so that the concave portion overlaps an observation visual field of the observation unit when the distal end cap for an endoscope is attached to the insertion end portion.
12. The distal end cap for an endoscope according to claim 1, wherein the concave portion is disposed so as to be adjacent to an illumination unit disposed on the insertion end portion in a radial direction of the distal end cap for an endoscope so that the concave portion overlaps an illumination range of the illumination unit when the distal end cap for an endoscope is attached to the insertion end portion.
13. An endoscope apparatus comprising:
an endoscope; and
the distal end cap for an endoscope according to claim 1 removably attached to an insertion end portion disposed on the endoscope.