Patent Description:
Programmers strive to write software (e.g., code) that is free from defects. However, programmers can often make simple, sometimes typographic, mistakes. Correction of such mistakes might consume an inordinate amount of time and/or resources to identify and/or correct.

<CIT> relates to detecting and correcting errors in software, such as in source code, using machine learning.

<CIT> relates to a computer-implemented method of detecting a likely software malfunction.

<CIT> relates to providing an active learning source code review framework.

<CIT> relates to a machine learning model being trained to infer the probability of the presence of categories of a software bug in a source code file.

The figures are not to scale. In general, the same reference numbers will be used throughout the drawing(s) and accompanying written description to refer to the same or like parts. As used herein, connection references (e.g., attached, coupled, connected, and joined) may include intermediate members between the elements referenced by the connection reference and/or relative movement between those elements unless otherwise indicated. As such, connection references do not necessarily infer that two elements are directly connected and/or in fixed relation to each other. As used herein, stating that any part is in "contact" with another part is defined to mean that there is no intermediate part between the two parts.

Unless specifically stated otherwise, descriptors such as "first," "second," "third," etc. are used herein without imputing or otherwise indicating any meaning of priority, physical order, arrangement in a list, and/or ordering in any way, but are merely used as labels and/or arbitrary names to distinguish elements for ease of understanding the disclosed examples. " In such instances, it should be understood that such descriptors are used merely for identifying those elements distinctly that might, for example, otherwise share a same name. As used herein "substantially real time" refers to occurrence in a near instantaneous manner recognizing there may be real world delays for computing time, transmission, etc. Thus, unless otherwise specified, "substantially real time" refers to real time +/- <NUM> second.

Programmers strive to write software (e.g., computer executable instructions, scripts, code, etc.) that is free from defects. Unfortunately, human programmers are prone to making mistakes, sometimes known as bugs, in their software. Such errors can cause operational error in the software and require the programmer to "debug" the software to find and correct the problem. In some examples, such mistakes might not be immediately apparent, and might only be discovered after identifying that the software does not function in an expected manner. This may not occur until the software is widely distributed to end users and can cause significant technical and/or commercial problems.

Approximately half of all software development time is spent debugging code. Therefore, even the smallest fraction of automation in the space of debugging could result in a notable time savings and improve programmer productivity globally. Examples disclosed herein can be used to automatically detect potential defects in control structures (e.g., conditional execution streams using "if' statements, looping execution streams using "for" and "while" loops, etc.) using machine learning. Moreover, the detection of such defects can be reinforced using human feedback to improve the machine learning process.

As noted above, roughly half of all software development time is in the space of debugging. Debugging is defined broadly herein as any activity related to identifying, tracking, root causing, and/or fixing of software bugs (e.g., errors). One specific class of bugs are those associated with control structures, such as if statements.

<FIG> illustrates a sample set of instructions <NUM> that includes an unintended defect. <FIG> illustrates an alternative sample set of instructions <NUM> that is free of the unintended defect of <FIG>. The example instructions of <FIG> are presented in the programming language C++. However, it should be understood that any other programming language that uses control structures might additionally or alternatively be used.

In the example set of instructions <NUM> of <FIG>, it is the programmer's intention to set the variable 'x' equal to <NUM> if 'x' is not already that value upon evaluation. Otherwise, 'x' should be set to <NUM> by way of the increment function (e.g., ++x;). Stated differently, if 'x' is equal to <NUM>, then increment 'x', otherwise set 'x' to <NUM>. Unfortunately, due to a one character syntax error identified by arrow <NUM>, this code always sets 'x' to the value of <NUM>. This is because the programmer had accidentally omitted a second '=' sign in the conditional if statement. The omission of this '=' transforms this operation from being a control structure condition equality evaluation (i.e., "if (x == <NUM>)"), to an assignment operation which always returns true after the assignment is performed (i.e., "x = <NUM>"), thereby causing execution of the '++x" instruction.

In the illustrated example of <FIG>, the conditional statement <NUM> uses a double equals '==' to specify the condition equality evaluation. An aspect of this example programming scenario that can make this type of bug particularly challenging is that the assignment of variables within conditionals is considered proper syntax in C/C++. In other words, the code "if (x = <NUM>)" is syntactically correct, despite not being what the programmer had intended. As such, a compiler will not identify this as a syntax error to bring the programmers attention to the error. Moreover, the instructions of <FIG> is a programming behavior that is seldom used. For example, use of the syntax 'if (x=<NUM>)' is typically considered a typographical error that consists of a single mistyped character. For these reasons, bugs of this kind can be some of the most notoriously difficult ones for humans to identify through manual and/or visual inspection.

Example approaches disclosed herein utilize a self-supervised learning system to learn the appropriate control structure signatures for a given programming language across a given training repository of code. Using a trained model, example approaches disclosed herein enable identification of potential software defects for presentation to a programmer. Such defects correspond to situations in which the software does not, for example, follow traditional syntax for a given control structure. The presentation of such non-traditional syntax identifications enables the programmer to more easily debug software. Using the non-traditional syntax identifications, the programmer may provide reinforcement learning by, for example, identifying the non-traditional syntax as a bug (or not). Such reinforcement learning can be used to refine the model and improve accuracy over time.

Example approaches disclosed herein do not rely upon labeled training data. Thus, programmers are not required to explicitly identify whether code is buggy or not. In this manner, many general programming language control structure patterns can be quickly learned for a given programming language. Once those patterns are learned, example approaches disclosed herein can identify, with varying degrees of confidence, potential bugs due to deviations from the learned patterns. Reinforcement learning (e.g., continual improvement of the learned information) may be used to, for example, increase or decrease the confidence level for potential defects, which can result in a dynamically improved system in identifying defects. Example approaches are programming language agnostic, meaning that theoretical underpinnings of the approaches disclosed herein are applicable to any programming language and/or script that can exhibit defects in control structures.

<FIG> is a schematic illustration of an example system <NUM> constructed in accordance with teachings of this disclosure to facilitate self-supervised software defect detection. The example system <NUM> of <FIG> operates upon instructions used for training <NUM> that are stored in an instruction repository <NUM>. More specifically, the instructions <NUM> are analyzed by a defect detector <NUM> to enable later analysis of instructions to be debugged <NUM>. The defect detector <NUM>, when reviewing the instructions <NUM>, attempts to identify potential defects (e.g., bugs) in the instructions <NUM>.

The example instructions <NUM> may represent any type of instructions including, for example, source code written in one or more programming languages. In examples disclosed herein, the instructions <NUM> are written in a language that includes control structures. As used herein, a control structure is any instruction or set of instructions that control how a program is to be executed. Different control structures may exist and/or may appear differently in the context of different programming languages. The instructions <NUM> represent previously written code that functions as intended. In other words, the instructions <NUM> are generally bug-free.

The example instruction repository <NUM> of the illustrated example of <FIG> is implemented by any type of storage device (e.g., any type of memory and/or storage disc for storing data such as, for example, flash memory, magnetic media, optical media, solid state memory, hard drive(s), thumb drive(s), etc. Furthermore, the data stored in the example instruction repository <NUM> may be in any data format such as, for example, binary data, comma delimited data, tab delimited data, structured query language (SQL) structures, etc. While, in the illustrated example, the instruction repository <NUM> is illustrated as a single device, the example instruction repository <NUM> and/or any other data storage device(s) described herein may be implemented by any number and/or type(s) of devices (e.g., memories). In the illustrated example of <FIG>, the example instruction repository <NUM> stores the instructions <NUM>. The example instruction repository <NUM> may be implemented by, for example, a public instruction repository such as, for example, a repository hosted by GitHub, Inc. In some examples, the instruction repository <NUM> is additionally or alternatively implemented as a private instruction repository.

The example instructions <NUM> shown in <FIG> represent instructions to be analyzed by the defect detector <NUM> for defect detection. In this manner, the instructions <NUM> may be stored in any storage device at any location accessible by the defect detector <NUM> including, for example, a local hard disk drive, local memory, a remote instruction repository (e.g., the instruction repository <NUM>), etc..

The example defect detector <NUM> of the illustrated example of <FIG> includes programming language selector <NUM>, a template repository <NUM>, an instruction gatherer <NUM>, a control structure miner <NUM>, a cluster generator <NUM>, a control structure data store <NUM>, a snippet ranker <NUM>, a syntax comparator <NUM>, and a defect presenter <NUM>. In operation, the example defect detector <NUM> analyzes instructions stored in the instruction repository <NUM> to learn common syntaxes used in a given programming language. The defect detector <NUM> uses the learned common syntaxes to attempt to detect defects in the instructions <NUM>.

The example programming language selector <NUM> of the illustrated example of <FIG> identifies a programming language of the instructions to be analyzed (e.g., either from the instruction repository <NUM> or the instructions to be analyzed for defects <NUM>). In examples disclosed herein, the programming language is identified based on a file extension associated with the instructions. For example, an instruction file having an extension of ". cpp" may be identified using the C++ programming language. However, other approaches for identifying a programming language may additionally or alternatively be used such as, for example, automatically analyzing the syntactic structures of the instructions.

Such an identification of the programming language performed by the programming language selector <NUM> is useful as, for example, different programming language(s) can have slightly varied, but similar, syntax. What may be a bug (e.g., resulting in unintended functionality) if written in one programming language, may result in intended functionality if written in another language.

The example template repository <NUM> of the illustrated example of <FIG> is implemented by any storage device (e.g., memory, structure, and/or storage disc for storing data such as, for example, flash memory, magnetic media, optical media, solid state memory, hard drive(s), thumb drive(s), etc). Furthermore, the data stored in the example template repository <NUM> may be in any data format such as, for example, binary data, comma delimited data, tab delimited data, structured query language (SQL) structures, etc. While, in the illustrated example, the template repository <NUM> is illustrated as a single device, the example template repository <NUM> and/or any other data storage devices described herein may be implemented by any number and/or type(s) of memories.

In the illustrated example of <FIG>, the example template repository <NUM> stores skeletal structures of known control structures for a given programming language. In some examples, the template repository <NUM> is populated with known control structures by manual input. For example, a programmer may provide skeletal structures of control structures used in the programming language (e.g., if statements, where statements, for each statements, do until statements, etc.). In some alternative examples, the identification of the skeletal structures may be identified by an automated extraction process. In some examples, multiple template repositories may be used corresponding to different programming languages. In some other examples, a single template repository may be used, and may include additional identifiers to accommodate identification of the programming language to which a skeletal structure corresponds.

The example instruction gatherer <NUM> of the illustrated example of <FIG> access instructions stored in the instruction repository <NUM> and/or other instructions (e.g., the instructions <NUM>). In examples disclosed herein, the instruction repository <NUM> is accessed based on user-provided configuration information including, for example, a uniform resource locator (URL) and/or uniform resource indicator (URI) for the resource, a username, a password, etc. The instruction gatherer <NUM> accesses the instruction repository <NUM> to, for example, enable the defect detector <NUM> to learn common syntaxes used in the instruction repository. Such common syntaxes can later be used by the defect detector <NUM> to analyze the instructions <NUM> to attempt to detect a defect.

When attempting to detect the defect, the example instruction gatherer <NUM> identifies an instruction to be analyzed (e.g., the instruction to be analyzed <NUM>). In some examples, the instruction gatherer <NUM> (and/or more generally, the example defect detector <NUM>) may be implemented as a part of an integrated development environment (IDE), such that code analysis is performed on the fly (e.g., while a programmer is writing code). In such an example, the code analysis may be triggered by, for example, saving of the software (e.g., the instructions to be analyzed <NUM>), a threshold amount of time elapsing from a prior analysis, entry of an instruction to compile the software (e.g., the instructions to be analyzed <NUM>), an instruction from the programmer to perform the analysis, etc. Alternatively, the instruction gatherer <NUM> may be implemented as part of a cloud solution that, for example, periodically scans a repository to identify potential bugs.

The example control structure miner <NUM> of the illustrated example of <FIG> mines the instruction repository <NUM> to identify control structures. The example control structure miner <NUM> identifies a control structure based on information stored in the template repository <NUM>. The example control structure miner <NUM> inserts information into the control structure data store <NUM> representative of control structures identified in the instruction repository <NUM>. The inserted information includes control structure instances, referred to as a code snippet. In some examples, the code snippet may include surrounding closures (e.g., brackets and/or other syntax related to the control structure).

The example cluster generator <NUM> of the illustrated example of <FIG> analyzes the control structure data store <NUM> to assign each code snippet identified by the control structure miner <NUM> to a particular control structure type, thereby separating code snippets by the type of control structure that they represent. Once all control structure instances are type-assigned (i.e., placed in their appropriate buckets), the example cluster generator <NUM> performs a pairwise code similarity analysis for each code pair that exists in each bucket. For example, if a given bucket of control structures included four code snippets, the example cluster generator <NUM> would perform the code similarity analysis on the following pairs: <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>. Using the similarity scores, the example cluster generator <NUM> generates clusters within each control structure type.

The example control structure data store <NUM> of the illustrated example of <FIG> is implemented by any storage device (e.g., memory, structure, and/or storage disc for storing data such as, for example, flash memory, magnetic media, optical media, solid state memory, hard drive(s), thumb drive(s), etc). Furthermore, the data stored in the example control structure data store <NUM> may be in any data format such as, for example, binary data, comma delimited data, tab delimited data, structured query language (SQL) structures, etc. While, in the illustrated example, the control structure data store <NUM> is illustrated as a single device, the example control structure data store <NUM> and/or any other data storage devices described herein may be implemented by any number and/or type(s) of memories. In the illustrated example of <FIG>, the example control structure data store <NUM> stores code snippets and additional information concerning those code snippets including, for example, a type of the control structure represented by the code snippet, a cluster identifier of the code snippet, and an indication of whether the code snippet is a "golden" snippet.

As shown in the illustrated example of <FIG>, the control structure data store <NUM> includes three types of control structures <NUM>, <NUM>, <NUM>. In the illustrated example of <FIG>, the first control structure type <NUM> includes a first cluster <NUM> having three code snippets, two of which are labeled as "golden" snippets (represented by the shading of the blocks representing the code snippets). The second control structure type <NUM> includes two clusters: a second cluster <NUM> and a third cluster <NUM>. The second example cluster <NUM> includes three code snippets, two of which are labeled as "golden" snippets. The third example cluster <NUM> includes four code snippets, two of which are labeled as "golden" snippets. The third control structure type <NUM> includes a fourth cluster <NUM>. The fourth example cluster <NUM> includes six code snippets, two of which are labeled as "golden" snippets.

While three control structure types are shown in the illustrated example of <FIG>, any number of control structure types may additionally or alternatively be used. Moreover, any number of clusters may be used within each of the example control structure types <NUM>, <NUM>, <NUM>. Furthermore, any number of code snippets may be labeled as "golden" snippets within each of those clusters. For example, while in the illustrated example of <FIG>, two snippets are labeled as "golden" within each of the clusters, in some examples, different numbers of clusters may be labeled as "golden" within some or all of the clusters.

In the illustrated example of <FIG>, a single programming language is represented by the code snippets (grouped into clusters and/or control structure types). In some examples, to accommodate separate programming languages, separate control structure data stores are used. However, in some other examples, a single control structure data store is used, and may additionally include information identifying the programming language of each of the code snippets, to allow for programming language based analysis to be performed.

The example snippet ranker <NUM> of the illustrated example of <FIG> performs a ranking analysis to identify one or more "golden" snippets. As used herein, a "golden" snippet (which may also be referred to as a reference snippet, a clean snippet, a bug-free snippet, etc.) is a code snippet that has been identified as being bug-free. Such identification may be the result of an automated analysis and/or a manual identification of a code snippet being bug-free. Conversely, a snippet that is not referred to as a "golden" snippet may represent bug-free code (e.g., has not yet been identified as being bug-free) or alternatively, may include a bug. The code snippets are then stored in the control structure database <NUM> the by the snippet ranker <NUM> along with the identification of whether the snippet is considered a "golden" snippet. As a result of the analysis, other software <NUM> can later be analyzed to identify deviations from those "golden" snippets, which may be represent potential bugs.

The example syntax comparator <NUM> of the illustrated example of <FIG> analyzes syntax of control structures that may include a defect and one or more "golden" snippets, to determine a level of similarity. In examples disclosed herein, the similarity is determined by using a precise syntax code similarity mechanism, such as, for example, an abstract syntax tree. Such an analysis enables the example syntax comparator <NUM> to identify minor syntax deviations in a generally semantically similar grouping that may be the source of a bug. In examples disclosed herein, the similarity analysis performed by the syntax comparator <NUM> results in creation of a score representing a degree of similarity between the control structure to analyze and the golden snippet. In some examples, the score may identify the similarity with a score from zero (no similarity) to one (perfect similarity). However, any other approach to identifying a level of similarity may additionally or alternatively be used.

Using the similarity score, the example syntax comparator <NUM> determines whether there is a minor syntax deviation from the golden snippet to the control structure to be analyzed. A minor deviation can be detected when, for example, the similarity score meets or exceeds a lower threshold (e.g.,. <NUM>, or <NUM>% similarity), and does not meet or exceed an upper threshold (e.g.,. <NUM>, or <NUM>% similarity). Using the upper threshold ensures code snippets will be flagged as buggy when they do not perfectly match the golden snippet (e.g., indicating a potential bug). Using the lower threshold ensures that code snippets will not be flagged as buggy when there is no correspondence to the golden snippet. Of course, any other similarity threshold values may additionally or alternatively be used. Adjusting the similarity threshold values may serve to, for example, reduce false positive and/or false negative identifications of potentially buggy instructions.

In response to the syntax comparator <NUM> detecting the minor syntax deviation, the example defect presenter <NUM> of the illustrated example of <FIG>, flags the control structure as potentially buggy. The defect presenter <NUM> presents the potentially buggy control structure to the programmer (e.g., a user), to enable the programmer to address the potentially buggy code. The defect presenter may present the identification of the potentially buggy code in different manners based on, for example, whether the defect detector <NUM> is implemented in, for example, an integrated development environment (IDE), a cloud repository analysis server, etc. In some examples, the defect presenter <NUM> causes presentation of a pop-up message and/or other alert to the programmer to identify the potential defect. In other examples, the defect presenter <NUM> may cause a message (e.g., an email message) to be communicated to the programmer to identify the defect. In some examples, a suggested correction may be proposed based on the identified golden snippet, to remediate the defect.

The programmer may, in response to the identification of the potential defect, select a correction to be applied to the buggy control structure (e.g., the correction based on the "golden" snippet). In such an example, the correction may be applied to the buggy control structure by the instruction gatherer <NUM> via the defect presenter <NUM> and/or the interface whose presentation was caused by the defect presenter <NUM>. Alternatively, the programmer may indicate that the control structure is not buggy (e.g., that a false identification of a defect has occurred).

While an example manner of implementing the defect detector <NUM> is illustrated in <FIG>, one or more of the elements, processes and/or devices illustrated in <FIG> may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the programming language selector <NUM>, the example instruction gatherer <NUM>, the example control structure miner <NUM>, the example cluster generator <NUM>, the example snippet ranker <NUM>, the example syntax comparator <NUM>, the example defect presenter <NUM>, and/or, more generally, the example defect detector <NUM> of <FIG> may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example instruction gatherer <NUM>, the example control structure miner <NUM>, the example cluster generator <NUM>, the example snippet ranker <NUM>, the example syntax comparator <NUM>, the example defect presenter <NUM>, and/or, more generally, the example defect detector <NUM> of <FIG> could be implemented by one or more analog or digital circuit(s), logic circuits, programmable processor(s), programmable controller(s), graphics processing unit(s) (GPU(s)), digital signal processor(s) (DSP(s)), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)). When reading any of the apparatus or system claims of this patent to cover a purely software and/or firmware implementation, at least one of the example instruction gatherer <NUM>, the example control structure miner <NUM>, the example cluster generator <NUM>, the example snippet ranker <NUM>, the example syntax comparator <NUM>, the example defect presenter <NUM>, and/or, more generally, the example defect detector <NUM> of <FIG> is/are hereby expressly defined to include a non-transitory computer readable storage device or storage disk such as a memory, a digital versatile disk (DVD), a compact disk (CD), a Blu-ray disk, etc. including the software and/or firmware. Further still, the example defect detector <NUM> of <FIG> may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated in <FIG>, and/or may include more than one of any or all of the illustrated elements, processes and devices. As used herein, the phrase "in communication," including variations thereof, encompasses direct communication and/or indirect communication through one or more intermediary components, and does not require direct physical (e.g., wired) communication and/or constant communication, but rather additionally includes selective communication at periodic intervals, scheduled intervals, aperiodic intervals, and/or one-time events.

Flowcharts representative of example hardware logic, machine readable instructions, hardware implemented state machines, and/or any combination thereof for implementing the defect detector <NUM> of <FIG> are shown in <FIG>, <FIG>, <FIG>, and/or <NUM>. The machine readable instructions may be one or more executable programs or portion(s) of an executable program for execution by a computer processor and/or processor circuitry, such as the processor <NUM> shown in the example processor platform <NUM> discussed below in connection with <FIG>. The program may be embodied in software stored on a non-transitory computer readable storage medium such as a CD-ROM, a floppy disk, a hard drive, a DVD, a Blu-ray disk, or a memory associated with the processor <NUM>, but the entire program and/or parts thereof could alternatively be executed by a device other than the processor <NUM> and/or embodied in firmware or dedicated hardware. Further, although the example program is described with reference to the flowchart illustrated in <FIG>, <FIG>, <FIG>, and/or <NUM>, many other methods of implementing the example defect detector <NUM> may alternatively be used. For example, the order of execution of the blocks may be changed, and/or some of the blocks described may be changed, eliminated, or combined. Additionally or alternatively, any or all of the blocks may be implemented by one or more hardware circuits (e.g., discrete and/or integrated analog and/or digital circuitry, an FPGA, an ASIC, a comparator, an operational-amplifier (op-amp), a logic circuit, etc.) structured to perform the corresponding operation without executing software or firmware. The processor circuitry may be distributed in different network locations and/or local to one or more devices (e.g., a multi-core processor in a single machine, multiple processors distributed across a server rack, etc).

The machine readable instructions described herein may be stored in one or more of a compressed format, an encrypted format, a fragmented format, a compiled format, an executable format, a packaged format, etc. Machine readable instructions as described herein may be stored as data or a data structure (e.g., portions of instructions, code, representations of code, etc.) that may be utilized to create, manufacture, and/or produce machine executable instructions. For example, the machine readable instructions may be fragmented and stored on one or more storage devices and/or computing devices (e.g., servers) located at the same or different locations of a network or collection of networks (e.g., in the cloud, in edge devices, etc.). The machine readable instructions may require one or more of installation, modification, adaptation, updating, combining, supplementing, configuring, decryption, decompression, unpacking, distribution, reassignment, compilation, etc. in order to make them directly readable, interpretable, and/or executable by a computing device and/or other machine. For example, the machine readable instructions may be stored in multiple parts, which are individually compressed, encrypted, and stored on separate computing devices, wherein the parts when decrypted, decompressed, and combined form a set of executable instructions that implement one or more functions that may together form a program such as that described herein.

In another example, the machine readable instructions may be stored in a state in which they may be read by processor circuitry, but require addition of a library (e.g., a dynamic link library (DLL)), a software development kit (SDK), an application programming interface (API), etc. in order to execute the instructions on a particular computing device or other device. In another example, the machine readable instructions may need to be configured (e.g., settings stored, data input, network addresses recorded, etc.) before the machine readable instructions and/or the corresponding program(s) can be executed in whole or in part. Thus, machine readable media, as used herein, may include machine readable instructions and/or program(s) regardless of the particular format or state of the machine readable instructions and/or program(s) when stored or otherwise at rest or in transit.

As mentioned above, the example processes of <FIG>, <FIG>, <FIG>, and/or <NUM> may be implemented using executable instructions (e.g., computer and/or machine readable instructions) stored on a non-transitory computer and/or machine readable medium such as a hard disk drive, a flash memory, a read-only memory, a compact disk, a digital versatile disk, a cache, a random-access memory and/or any other storage device or storage disk in which information is stored for any duration (e.g., for extended time periods, permanently, for brief instances, for temporarily buffering, and/or for caching of the information). As used herein, the term non-transitory computer readable medium is expressly defined to include any type of computer readable storage device and/or storage disk and to exclude propagating signals and to exclude transmission media.

<FIG> is a flowchart representative of example machine readable instructions <NUM> which may be executed to implement the example defect detector of <FIG>. In particular, the instructions of <FIG> enable the defect detector to initialize and learn control structures for a programming language. The example machine readable instructions <NUM> begin execution when the example programming language selector <NUM> accesses an identification of a selected programming language. (Block <NUM>). In examples disclosed herein, a single model (e.g., control structure data store <NUM>) is used for each different programming language. However, in some examples, multiple programming languages may be accounted for in a single model. In some examples, the programming language may be used as an input to, for example, allow for selection of sub-components of the control structure data store <NUM> specific to the specific programming language.

The example control structure miner <NUM> accesses a skeletal structure of known control structures for the selected programming language. (Block <NUM>). In examples disclosed herein, the skeletal structures of the known control structures are stored in the example template repository <NUM>. In some examples, the template repository <NUM> is populated with known control structures by manual input. For example, a programmer may provide skeletal structures of control structures used in the programming language (e.g., if statements, where statements, for each statements, do until statements, etc.). In some alternative examples, the identification of the skeletal structures may be identified by an automated extraction process.

The example instruction accessor <NUM> then configures access to the instruction repository <NUM>. (Block <NUM>). In examples disclosed herein, the repository is accessed based on user-provided configuration information including, for example, a uniform resource locator (URL) and/or uniform resource indicator (URI) for the resource, a username, a password, etc..

The example control structure miner <NUM> mines the instruction repository and inserts information into the control structure data store <NUM>. (Block <NUM>). The inserted information includes control structure instances, referred to as a code snippet. In some examples, the code snippet may include surrounding closures (e.g., brackets and/or other syntax related to the control structure). The example cluster generator <NUM> analyzes the control structure data store <NUM> to assign each code snippet a particular control structure type, thereby separating code snippets by the type of control structure that they represent. (Block <NUM>).

Once all control structure instances are type-assigned (i.e., placed in their appropriate buckets), the example cluster generator <NUM> performs a pairwise code similarity analysis for each code pair that exists in each bucket. (Block <NUM>). For example, if a given bucket of control structures included four code snippets, the example cluster generator <NUM> would perform the code similarity analysis on the following pairs: <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>, <<NUM>, <NUM>>. Using the similarity scores, the example cluster generator <NUM> generates clusters within each control structure type. (Block <NUM>). An example approach to generating clusters within each control structure type is described in further detail in connection with <FIG>, below.

Depending on the size of code corpus used, the example clustering may result in multiple semantic grouping clusters for each bucket. For example, there may be <NUM> different semantic variants (e.g., groups) for "for" loops: (i) one where iterators are used, (ii) one where zero-based integers are set to some minimum and iterate until some max value is reached, using a monotonically increasing mechanism, and (iii) one where zero-based integers are set to a maximum and iterate until some minimum is reached, using a monotonically decreasing mechanism. Any number of semantic grouping clusters may be identified for a particular type of control structure. In practice, as few as zero clusters for a control structure type may be identified (e.g., if there are zero code instances identified for the control structure type). In some examples, hundreds, or even thousands, of clusters may be identified for a given type of control structure.

Once all control structure instances are type-assigned (i.e., placed in their appropriate buckets), and clusters within those types of control structures are identified, the example snippet ranker <NUM> performs a ranking analysis to identify one or more "golden" snippets. (Block <NUM>). An example approach for ranking code snippets to identify one or more "golden" snippets is described below in further detail in connection with <FIG>. As used herein, a "golden" snippet (which may also be referred to as a reference snippet, a clean snippet, a bug-free snippet, etc.) is a code snippet that has been identified as being bug-free. Such identification may be the result of an automated analysis and/or a manual identification of a code snippet being bug-free. Conversely, a snippet that is not referred to as a "golden" snippet may represent bug-free code (e.g., has not yet been identified as being bug-free) or alternatively, may include a bug. The code snippets are then stored in control structure database <NUM> the by the snippet ranker <NUM> along with the identification of whether the snippet is considered a "golden" snippet. (Block <NUM>). As a result of the process of <FIG>, software can later be analyzed to identify deviations from those "golden" snippets, which may be represent potential bugs. The example process of <FIG> then terminates, but may be repeated to, for example, identify semantics and "golden" snippets for another programming language, re-identify semantics and "golden" snippets the programming language identified at block <NUM>, use a different instruction repository, etc..

<FIG> is a flowchart representative of example machine readable instructions <NUM> which may be executed to implement the example defect detector of <FIG>. In particular, the instructions of <FIG> enable the defect detector to identify and generate clusters per control structure type. The example process <NUM> of the illustrated example of <FIG> begins when the example cluster generator identifies a control structure for processing. (Block <NUM>). In an initial iteration, the example cluster generator identifies a first control structure. If a control structure is identified (e.g., block <NUM> returns a result of YES), the example cluster generator generates clusters, based on a clustering analysis of the code instances within the control structure and the pair-wise similarity scores identified in block <NUM> of <FIG>. (Block <NUM>). Each code instance within the code structure is assigned a unique cluster identifier within the generated clusters. (Block <NUM>). Control proceeds to block <NUM>, where the example process is repeated for each of the control structures. The example process <NUM> of <FIG> terminates when no further control structures exist (e.g., block <NUM> returns a result of NO).

<FIG> is a flowchart representative of example machine readable instructions <NUM> which may be executed to implement the example defect detector of <FIG>. In particular, the instructions of <FIG> enable the defect detector to rank code snippets as a "golden" snippet. Once all semantics clusters for each control type bucket, each cluster is sent through a pairwise natural language processing similarity and a pairwise code similarity ranking system. The code pairs with the largest overall NLP and code similarity ranks are then considered "golden" instances of each clustered group. The example process <NUM> of the illustrated example of <FIG> begins when the example snippet ranker <NUM> identifies a code snippet within the control structure data store. (Block <NUM>). The example snippet ranker <NUM> calculates a ranking score based on a pairwise similarity analysis (e.g., a semantic analysis) and/or a natural language processing (NLP) analysis (e.g., a syntactic analysis). (Block <NUM>). In examples disclosed herein, the pairwise similarity analysis and/or NLP analysis is performed in the context of the other code snippets within the same cluster. In examples disclosed herein, the ranking score is generated using, for example, a harmonic mean of the scores of the similarity analysis and NLP analysis. However, any other approach for generating a ranking score may additionally or alternatively be used. The example snippet ranker <NUM> stores the ranking score in association with the code snippet. (Block <NUM>).

Control proceeds to block <NUM>, where ranking scores are generated for each code snippet. Upon generation of the ranking scores (e.g., upon block <NUM> returning a result of NO), the example snippet ranker <NUM> rank orders the code snippets within each cluster. (Block <NUM>). Within each cluster, the example snippet ranker <NUM> labels the top N ranked code snippets as a "golden" snippet. (Block <NUM>). While in the illustrated example of <FIG>, a fixed number of code snippets are labeled as "golden", any other approach to selecting code snippets to be labeled as "golden" may additionally or alternatively be used. For example, a top percentage of code snippets (e.g., the top <NUM>% of snippets) may be identified as "golden", a threshold ranking score may be used to determine whether a code snippet should be considered "golden," etc. The example process <NUM> of <FIG> then terminates.

<FIG> is a flowchart representative of example machine readable instructions <NUM> which may be executed to implement the example defect detector of <FIG>. In particular, the instructions of <FIG> enable the defect detector to identify a software defect. The example process <NUM> of <FIG> begins when the example instruction gatherer <NUM> identifies an instruction and/or set of instructions to analyze. (Block <NUM>). In some examples, the instruction gatherer <NUM> may be implemented as a part of an integrated development environment (IDE), such that code analysis is performed on the fly (e.g., while a programmer is writing code). In such an example, the code analysis may be triggered by, for example, saving of the software, a threshold amount of time elapsing from a prior analysis, entry of an instruction to compile the software, an instruction from the programmer to perform the analysis, etc. Alternatively, the instruction gatherer <NUM> may be implemented as part of a cloud solution that, for example, periodically scans a repository to identify potential bugs.

The example programming language selector <NUM> identifies the programming language of the instructions to be analyzed. (Block <NUM>). In examples disclosed herein, the programming language is identified based on a file extension associated with the instructions. However, other approaches for identifying a programming language may additionally or alternatively be used such as, for example, automatically analyzing the syntactic structures of the code snippet. Such an identification is useful as, for example, different programming language can have slightly varied, but similar, syntax. What may be a bug (e.g., resulting in unintended functionality) if written in one programming language, may result in intended functionality if written in another language. Thus, identification of the programming language in question, for selection of the corresponding control structure data store <NUM>, is important for accurately identifying potential defects.

The example control structure miner <NUM> identifies a control structure within the instructions. (Block <NUM>). In some examples, instructions to be analyzed may include multiple control structures for analysis. After having identified a control structure, the example control structure miner <NUM> identifies a type of the control structure. (Block <NUM>). In examples disclosed herein, the type of the control structure is identified based on the control structure templates stored in the template repository <NUM> in association with the programming language of the instruction.

The example syntax comparator <NUM> identifies a golden snippet against which the control structure to analyze is to be compared. (Block <NUM>). The example syntax comparator <NUM> compares the control structure to be analyzed against the golden snippet to determine a level of similarity. (Block <NUM>). In examples disclosed herein, the similarity is determined by using a precise syntax code similarity mechanism, such as, for example, an abstract syntax tree. Such an analysis enables the example syntax comparator <NUM> to identify minor syntax deviations in a generally semantically similar grouping that may be the source of a bug. In examples disclosed herein, the similarity analysis performed by the syntax comparator <NUM> results in creation of a score representing a degree of similarity between the control structure to analyze and the golden snippet. In some examples, the score may identify the similarity with a score from zero (no similarity) to one (perfect similarity). However, any other approach to identifying a level of similarity may additionally or alternatively be used.

Using the similarity score, the example syntax comparator <NUM> determines whether there is a minor syntax deviation from the golden snippet to the control structure to be analyzed. (Block <NUM>). Such a minor deviation can be detected when, for example, the similarity score meets or exceeds a lower threshold (e.g.,. <NUM>, or <NUM>% similarity), and does not meet or exceed an upper threshold (e.g.,. <NUM>, or <NUM>% similarity). Using the upper threshold ensures code snippets will be flagged as buggy when they do not perfectly match the golden snippet (e.g., indicating a potential bug). Using the lower threshold ensures that code snippets will not be flagged as buggy when there is no correspondence to the golden snippet. Of course, any other similarity threshold values may additionally or alternatively be used. Adjusting the similarity threshold values may serve to, for example, reduce false positive and/or false negative identifications of potentially buggy instructions.

If a minor syntax deviation is not detected (e.g., block <NUM> returns a result of NO), the example syntax comparator <NUM> determines whether there are any additional "golden" snippets to analyze. (Block <NUM>). If there is an additional "golden" snippet to analyze (e.g., block <NUM> returns a result of YES), control returns to block <NUM>, where the process of blocks <NUM> through <NUM> is repeated until either a minor syntax deviation is detected (e.g., block <NUM> returns a result of YES), or no additional "golden" snippets remain to be analyzed for the identified type of the control structure (e.g., block <NUM> returns a result of NO). If no additional "golden" snippet exists to analyze (e.g., block <NUM> returns a result of NO), the example process <NUM> of <FIG> terminates.

Returning to block <NUM>, if the minor syntax deviation is detected (e.g., block <NUM> returns a result of YES), the example defect presenter <NUM> flags the control structure as potentially buggy. (Block <NUM>). The potentially buggy control structure is presented to the programmer (e.g., a user), to enable the programmer to address the potentially buggy code. (Block <NUM>). The identification of the potentially buggy code may be presented in different manners based on, for example, whether the defect detector <NUM> is implemented in, for example, an integrated development environment (IDE), a could repository analysis server, etc. In some examples, a pop-up message and/or other alert may be displayed to the programmer to identify the potential defect. In other examples, a message (e.g., an email message) may be communicated to the programmer to identify the defect. In some examples, a suggested correction may be proposed based on the identified golden snippet, to remediate the defect.

The programmer may, in response to the identification of the potential defect, select a correction to be applied to the buggy control structure (e.g., the correction based on the "golden" snippet). In such an example, the correction may be applied to the buggy control structure by the instruction gatherer <NUM>. (Block <NUM>). Alternatively, the programmer may indicate that the control structure is not buggy (e.g., that a false identification of a defect has occurred). The example snippet ranker <NUM> adds the control structure to the control structure data store <NUM> as a golden control structure. (Block <NUM>). Adding the control structure to the control structure data store <NUM> enables future instances of similar instructions to not be labeled as potentially buggy or, alternatively, enables correction of such potentially buggy software). The example process <NUM> of <FIG> then terminates, but may be repeated periodically and/or a-periodically as software is developed and/or maintained to attempt to identify potential defects.

<FIG> is a block diagram of an example processor platform <NUM> structured to execute the instructions of <FIG>, <FIG>, <FIG>, and/or <NUM> to implement the defect detector <NUM> of <FIG>. The processor platform <NUM> can be, for example, a server, a personal computer, a workstation, a self-learning machine (e.g., a neural network), a mobile device (e.g., a cell phone, a smart phone, a tablet such as an iPad™), a personal digital assistant (PDA), an Internet appliance, a DVD player, a CD player, a digital video recorder, a Blu-ray player, a gaming console, a personal video recorder, a set top box, a headset or other wearable device, or any other type of computing device.

For example, the processor <NUM> can be implemented by one or more integrated circuits, logic circuits, microprocessors, GPUs, DSPs, or controllers from any desired family or manufacturer. The hardware processor may be a semiconductor based (e.g., silicon based) device. In this example, the processor implements the example programming language selector <NUM>, the example instruction gatherer <NUM>, the example control structure miner <NUM>, the example cluster generator <NUM>, the example snippet ranker <NUM>, the example syntax comparator <NUM>, and the example defect presenter <NUM>.

The volatile memory <NUM> may be implemented by Synchronous Dynamic Random Access Memory (SDRAM), Dynamic Random Access Memory (DRAM), RAMBUS® Dynamic Random Access Memory (RDRAMR) and/or any other type of random access memory device.

The machine executable instructions <NUM> of <FIG>, <FIG>, <FIG>, and/or <NUM> may be stored in the mass storage device <NUM>, in the volatile memory <NUM>, in the non-volatile memory <NUM>, and/or on a removable non-transitory computer readable storage medium such as a CD or DVD.

A block diagram illustrating an example software distribution platform <NUM> to distribute software such as the example computer readable instructions <NUM> of <FIG> to third parties is illustrated in <FIG>. The example software distribution platform <NUM> may be implemented by any computer server, data facility, cloud service, etc., capable of storing and transmitting software to other computing devices. The third parties may be customers of the entity owning and/or operating the software distribution platform. For example, the entity that owns and/or operates the software distribution platform may be a developer, a seller, and/or a licensor of software such as the example computer readable instructions <NUM> of <FIG>. The third parties may be consumers, users, retailers, OEMs, etc., who purchase and/or license the software for use and/or re-sale and/or sub-licensing.

In the illustrated example, the software distribution platform <NUM> includes one or more servers and one or more storage devices. The storage devices store the computer readable instructions <NUM>, which may correspond to the example computer readable instructions of <FIG>, <FIG>, <FIG>, and/or <NUM>, as described above. The one or more servers of the example software distribution platform <NUM> are in communication with a network <NUM>, which may correspond to any one or more of the Internet and/or any of the example networks <NUM> described above. In some examples, the one or more servers are responsive to requests to transmit the software to a requesting party as part of a commercial transaction. Payment for the delivery, sale and/or license of the software may be handled by the one or more servers of the software distribution platform and/or via a third party payment entity. The servers enable purchasers and/or licensors to download the computer readable instructions <NUM> from the software distribution platform <NUM>. For example, the software, which may correspond to the example computer readable instructions of <FIG>, <FIG>, <FIG>, and/or <NUM>, may be downloaded to the example processor platform <NUM>, which is to execute the computer readable instructions <NUM> to implement the defect detector <NUM> of <FIG>. In some example, one or more servers of the software distribution platform <NUM> periodically offer, transmit, and/or force updates to the software (e.g., the example computer readable instructions <NUM> of <FIG>) to ensure improvements, patches, updates, etc. are distributed and applied to the software at the end user devices.

Claim 1:
A method (<NUM>) for detecting a defect in software, the method comprising:
identifying (<NUM>) a plurality of code snippets in an instruction repository (<NUM>), the code snippets to represent control structures, wherein a control structure indicates a set of instructions that control how a program is to be executed;
identifying (<NUM>) types of control structures of the code snippets;
generating a plurality of clusters of code snippets, the clusters of the code snippets corresponding to different types of control structures;
labeling (<NUM>) at least one code snippet of at least one of the clusters of the code snippets as at least one reference code snippet, wherein the at least one reference code snippet is a code snippet that has been identified as being bug-free; and
comparing (<NUM>) the at least one reference code snippet against a test code snippet to detect a defect in the test code snippet.