Skip to main content
9 votes
Accepted

What's role of software verification in modern software engineering

This is actually a surprisingly complex topic. Who verifies the verifiers? Have you heard of Ada/SPARK? Ada is a programming language which is mostly used in embedded contexts, including in military ...
Matthieu M.'s user avatar
4 votes

How to Generate Control flow graph from a Petri net model?

Since you are interested in generating test sequences automatically using colored Petri nets, note that it's not clear that you need reduction to control flow graphs (and dealing with all the related ...
ivcha's user avatar
  • 540
4 votes

What's role of software verification in modern software engineering

To be honest this feels like it's a question of just practicality and feasibility. The reality is that all of our systems are just so complex these days, that it's almost impossible to just verify ...
Minko_Minkov's user avatar
4 votes
Accepted

optimal testing strategy

in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense. This is the famous two egg problem where You are given ...
Amir-Mousavi's user avatar
3 votes
Accepted

Are there invariants in text processing problems?

Yes. One can find invariants in any program. The notion is well-defined and meaningful in any program (whether it is useful in practice is a different question). Normally identifying invariants is ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

How a Symbolic Evaluator Generates Test Input for this Example

Tools that solve problems like this often use a SMT (Satisfiability Modulo Theories) solver. This a SAT solver combined with a "theory solver" that can understand operations in some domain. For ...
Curtis F's user avatar
  • 1,043
3 votes
Accepted

Finding minimal and complete test sets for circuits

Yes. One can construct a Majella sequence of length $n \cdot 2^n + 1$, recursively. It's easy to see you can't do any better than this, so this is optimal. Definition. I'll say that a sequence $x_0,...
D.W.'s user avatar
  • 161k
2 votes

What is the theory behind testing fixes for intermittent bugs?

You juggle with "probabilities" without defining any. There are two different questions here. For practical programs, can I use random testing to establish that any given execution has close to 100%...
Raphael's user avatar
  • 72.6k
2 votes
Accepted

What to prove and how to prove it

I think you raise an important point, which is that in a high level language, specifications can be hard to distinguish from implementations. For example, in Coq, the specification of "The sum of the ...
cody's user avatar
  • 8,233
2 votes

How to test if my implementation of tree/graph data structures are correct?

Identify the representation invariants. Add assert statements to check that the representation invariant holds (sometimes called a repOK function). Use random testing to generate millions of test ...
D.W.'s user avatar
  • 161k
1 vote

Are Unit Tests Required if you have a good End to End Test?

This isn't really a CS question, more of a Software Engineering question. Still: If you find an error in an end-to-end test, and you can then replicate it in a simpler unit test, then you definitely ...
MSalters's user avatar
  • 895
1 vote
Accepted

Populating a vector of numbers to expose an error in a function implementation

Multilinear polynomials If you're willing to use probabilistic methods, I suggest using a randomized algorithm for polynomial identity testing. You want to test whether $f(x)=g(x)$ holds for all $x$, ...
D.W.'s user avatar
  • 161k
1 vote
Accepted

Problem with understanding the Mathematical Equations related to Testing Tool

They are statements about patterns of correct and incorrect code: For all call sites L1, there does not exist a store site L2 such that ... (and here I’m not clear—is that L2 may follow L1? Or that ...
D. Ben Knoble's user avatar
1 vote

How to test implementation details when there are multiple ways of implementing the algorithm, without reading the code?

To find out if it is e.g. doing binary search (or using hashing, or whatever) inside, you have to look at what it is doing. No way around it. Why would you insist on a particular algorithm? The whole ...
vonbrand's user avatar
  • 14.1k
1 vote

What to prove and how to prove it

It's not correct to say that in TLA+, the program is the specification. I don't know of any system where that is true. Rather, TLA+ is a way of writing a formal model of a system. You could think ...
D.W.'s user avatar
  • 161k
1 vote

Pseudocode for constructing control flow graph

To create a CFG you begin with an Abstract Syntax Tree (AST). So I assume you have an AST available. The first step is to collect the nodes in the tree into basic blocks. This step is optional but ...
Gaslight Deceive Subvert's user avatar
1 vote

How to choose the right input(s) to test my algorithm?

To achieve 100% coverage of all the cases, you'll probably need many test cases. You might want to do some reading on "test case generation". Typically, software developers think through the ...
D.W.'s user avatar
  • 161k
1 vote

How to choose the right input(s) to test my algorithm?

If you want to automatically explore the state space of a program, you could try a fuzzer like AFL. But usually programmers do this by running the program under a debugger and thinking a bit about how ...
adrianN's user avatar
  • 5,951

Only top scored, non community-wiki answers of a minimum length are eligible