I had idea in Mind, idea about storing numbers in computer memory in form of numerator and denominator / pl: 'licznik i mianownik' /, in an attempt to simplify precise calculations.
I wrote some code to factor numbers, to find prime factors of a number / pl: 'rozkład liczby na czynniki pierwsze' /.
But this code does more than just determining if number is prime, and if not - finding prime factors of this number. It stores paths and partial calculations, it gives not only one solution, but all of possible solutions, that perhaps can be used and reused in creative ways.
Then I had another idea - what if numbers were stored in such form, in form of factorization tree. Perhaps adding trees, or other operations on factorization trees would allow for some swift, abstract calculations.
Then I remembered Geometry with Linear Algbera, and neutral elements of operations on structures such as Groups, Rings and Fields / pl: 'Grupy, Pierścienie i Ciała' /.
What kind of FactorizationTree would be a neutral element of FactorizationTrees' Addition?
How about Multiplying FactorizationTrees?
I'll admit that most of this is just musings and considerings, I admit that I let my imagination run wild this time.
This blog has a place for ideas exploration, after all.
I might need to research following topics:
- Abstract Algebra / also known as Modern Algebra /,
/ Downloaded an ebook in .pdf file format /,
/ Polish edition of this book was published by WNT: 'Wydawnictwa Naukowo-Techniczne',
my favourite scientific & technical books publisher;
mostly that's why I chose this book over others, looked at table of contents list too;
WNT-published books are often recommended by Warsaw University as well;
Ebooks are more eco-friendly than printed books, and a smartphone is enough to read these /,
- Group Theory,
- Ring Theory,
- Field Theory,
- Inverse element / pl: 'element odwrotny' /,
- Binary operation / pl: 'działanie binarne' /,
- Homomorphism / pl: 'homomorfizm' /,
- Isomorphism / pl: 'izomorfizm' /.
Thursday, 16 April 2026
Sunday, 1 March 2026
'SOLID': Five Principles for Object-Oriented Software Quality.
In Object-Oriented Programming & Design, SOLID is a mnemonic acronym for five principles intended to make source code & design more understandable, flexible, and maintainable.
This means faster software construction/modification/debugging and lower overall project's costs (programmers are paid for their work-hours).
Software engineer and instructor Robert C. Martin introduced the basic principles of SOLID design in his 2000 paper: 'Design Principles and Design Patterns about software rot'. The SOLID acronym was coined around 2004 by Michael Feathers.
1. Single responsibility principle.
Every class should have only one responsibility, which means that a class should be responsible for only ONE 'thing'.
Importance:
Maintainability: When classes have a single, well-defined responsibility, they're easier to understand and modify.
Testability: It's easier to write unit tests for classes with a single focus.
Flexibility: Changes to one responsibility don't affect unrelated parts of the system.
2. Open–closed principle.
The open–closed principle (OCP) states that software entities should be open for extension, but closed for modification.
In other words, when we define a subclass, we can ask for less or same (less or same preconditions, as defined in class/method contract), and/or provide more or same (we still must provide what is defined in contract at the minimum, but we can also provide more).
Importance:
Extensibility: New features can be added without modifying existing code.
Stability: Reduces the risk of introducing bugs when making changes.
Flexibility: Adapts to changing requirements more easily.
3. Liskov substitution principle.
LSP requirement states that we must ensure that it's possible for a class to be replaced by any of its children (subclasses). Children classes inherit parent's behaviours, MUST NOT break the contract defined for the parent's class.
Importance:
Polymorphism: Enables the use of polymorphic behavior, making code more flexible and reusable.
Reliability: Ensures that subclasses adhere to the contract defined by the superclass.
Predictability: Guarantees that replacing a superclass object with a subclass object won't break the program.
4. Interface segregation principle.
The interface segregation principle (ISP) states that no code should be forced to depend on methods it does not use. ISP splits interfaces that are very large into smaller and more specific ones so that clients will only have to know about the methods that are of interest to them.
Importance:
Decoupling: Reduces dependencies between classes, making the code more modular and maintainable.
Flexibility: Allows for more targeted implementations of interfaces.
Avoids unnecessary dependencies: Clients don't have to depend on methods they don't use.
5. Dependency inversion principle.
The dependency inversion principle (DIP) states to depend upon abstractions, not upon concretes.
Importance:
Loose coupling: Reduces dependencies between modules, making the code more flexible and easier to test.
Flexibility: Enables changes to implementations without affecting clients.
Maintainability: Makes code easier to understand and modify.
See also:
> [ Design by Contract ],
> [ A few thoughts on code quality... ],
> [ Software Development & Quality ].
This means faster software construction/modification/debugging and lower overall project's costs (programmers are paid for their work-hours).
Software engineer and instructor Robert C. Martin introduced the basic principles of SOLID design in his 2000 paper: 'Design Principles and Design Patterns about software rot'. The SOLID acronym was coined around 2004 by Michael Feathers.
1. Single responsibility principle.
Every class should have only one responsibility, which means that a class should be responsible for only ONE 'thing'.
Importance:
Maintainability: When classes have a single, well-defined responsibility, they're easier to understand and modify.
Testability: It's easier to write unit tests for classes with a single focus.
Flexibility: Changes to one responsibility don't affect unrelated parts of the system.
2. Open–closed principle.
The open–closed principle (OCP) states that software entities should be open for extension, but closed for modification.
In other words, when we define a subclass, we can ask for less or same (less or same preconditions, as defined in class/method contract), and/or provide more or same (we still must provide what is defined in contract at the minimum, but we can also provide more).
Importance:
Extensibility: New features can be added without modifying existing code.
Stability: Reduces the risk of introducing bugs when making changes.
Flexibility: Adapts to changing requirements more easily.
3. Liskov substitution principle.
LSP requirement states that we must ensure that it's possible for a class to be replaced by any of its children (subclasses). Children classes inherit parent's behaviours, MUST NOT break the contract defined for the parent's class.
Importance:
Polymorphism: Enables the use of polymorphic behavior, making code more flexible and reusable.
Reliability: Ensures that subclasses adhere to the contract defined by the superclass.
Predictability: Guarantees that replacing a superclass object with a subclass object won't break the program.
4. Interface segregation principle.
The interface segregation principle (ISP) states that no code should be forced to depend on methods it does not use. ISP splits interfaces that are very large into smaller and more specific ones so that clients will only have to know about the methods that are of interest to them.
Importance:
Decoupling: Reduces dependencies between classes, making the code more modular and maintainable.
Flexibility: Allows for more targeted implementations of interfaces.
Avoids unnecessary dependencies: Clients don't have to depend on methods they don't use.
5. Dependency inversion principle.
The dependency inversion principle (DIP) states to depend upon abstractions, not upon concretes.
Importance:
Loose coupling: Reduces dependencies between modules, making the code more flexible and easier to test.
Flexibility: Enables changes to implementations without affecting clients.
Maintainability: Makes code easier to understand and modify.
See also:
> [ Design by Contract ],
> [ A few thoughts on code quality... ],
> [ Software Development & Quality ].
Wednesday, 17 December 2025
Occam's Razor.
In Philosophy, Occam's Razor is the problem-solving principle that recommends searching for explanations constructed with the smallest possible set of elements.
Attributed to William of Ockham, a 14th-century english philosopher and theologian, it is frequently cited and translated as:
'Entities must not be multiplied beyond necessity'.
... although Occam never used these exact words. Popularly, the principle is sometimes paraphrased as:
'Of competing theories, the simplest is to be preferred'.
Also, this philosophical razor advocates that when presented with competing theories, one should prefer the theory that requires the fewest assumptions.
So, in practice, when we have a set of competing theories, we should first select theories with least assumptions, then choose the simplest one from them.
Sources:
- Occam's Razor on Wikipedia,
- my own thinking.
Attributed to William of Ockham, a 14th-century english philosopher and theologian, it is frequently cited and translated as:
... although Occam never used these exact words. Popularly, the principle is sometimes paraphrased as:
Also, this philosophical razor advocates that when presented with competing theories, one should prefer the theory that requires the fewest assumptions.
So, in practice, when we have a set of competing theories, we should first select theories with least assumptions, then choose the simplest one from them.
Sources:
- Occam's Razor on Wikipedia,
- my own thinking.
Wednesday, 8 October 2025
Hacking Scripts in Python 3.
Writing Python scripts is an excellent exercise for learning this programming language.
... but.there's more to that as well, for hackers.
Sometimes tools are not available on attacked system, and even worse - we can't install these either.
But - as it happens often in practice, I read - if the target system has python interpreter, we can use our own scripts - we can use our own tools.
Here's list of some scripts that can be used in hacking - even if only as general ideas, to be enhanced and customized for our particular needs:
1. Introduction.
1.1. Hello World.
2. Basic Networking.
2.1. TCP Client,
2.2. TCP Server,
2.3. UDP Client,
2.4. UDP Server.
3. Webpage Scraping.
3.1. Words Count.
4. File Download/Upload.
4.1. File Download over HTTPS or over HTTP.
I'll try to keep the above list up-to-date, as I write more scripts.
... but.there's more to that as well, for hackers.
Sometimes tools are not available on attacked system, and even worse - we can't install these either.
But - as it happens often in practice, I read - if the target system has python interpreter, we can use our own scripts - we can use our own tools.
Here's list of some scripts that can be used in hacking - even if only as general ideas, to be enhanced and customized for our particular needs:
1. Introduction.
1.1. Hello World.
2. Basic Networking.
2.1. TCP Client,
2.2. TCP Server,
2.3. UDP Client,
2.4. UDP Server.
3. Webpage Scraping.
3.1. Words Count.
4. File Download/Upload.
4.1. File Download over HTTPS or over HTTP.
I'll try to keep the above list up-to-date, as I write more scripts.
Sunday, 21 September 2025
Artificial Intelligence & Ethical Hacking.
I've understood, and decided that AI can't be ignored anymore. I've asked the ChatGPT service the three questions, important questions for my pentesting career planning:
1. Can AI replace ethical hackers?
2. How pentesters can use AI to help them in their work?
3. Can AI analyze output of the LinPeas.sh script?
The 3rd question is an example, it shows how AI can be interacted with when a specific, tedious task is to be done.
Long answers short:
AI can augment human pentesters, to hasten some of their tedious work.
AI can, for example, be used to parse and interpret output of the LinPEAS.sh script, saving pentester a lot of time and effort during the post-exploitation phase, when one tries to escalate his or her privileges.
So, humans should remain in control, be the 'pentest leaders', that use AI for help in some of their tedious tasks.
To do their work well, however, the 'pentest leaders' should know & understand the nuances of the cybersecurity fields, especially the pentesting parts. We should be aware that AI will sometimes fail, and should be able to do some things manually, when this happens.
This can be very good news for pentesters, as human pentesters who will adapt to use AI in their work will be competitive, and will remain competitive in the job market.
Speaking abstractly:
As the History teaches us,
During the Times of Great Changes, those who Adapt will come Victorious,
Those who Oppose Changes will be left behind.
--
Important: Before using AI during the Real-Life Pentest (as opposed to Capture the Flag exercises on some hacking sites like the Hack the Box or Try Hack Me), check with lawyer if it's legal, if it's not violation of NDA or contract signed with customer.
Question #1:
Can AI Replace Ethical Hackers?
Answer:
That’s a deep question. Let’s break it down:
1. What ethical hackers do?
Ethical hackers (or penetration testers) simulate cyberattacks on systems to uncover vulnerabilities before malicious actors exploit them. Their role isn’t just technical — it also involves:
- Understanding business contexts and risks,
- Thinking creatively and unpredictably, like an attacker would.
- Communicating findings clearly to stakeholders.
- Advising on remediation strategies and balancing security with usability.
2. What AI can do today?
AI is already being applied in security testing and operations:
- Automation: AI can scan for known vulnerabilities, misconfigurations, and patterns at scale
much faster than humans.
- Exploit simulation: Some AI systems can chain together attack paths or fuzz inputs to find
weaknesses.
- Threat intelligence: AI can analyze vast amounts of threat data, flag anomalies, and
predict possible attack vectors.
- Red teaming tools: Emerging AI-driven platforms can mimic attacker behaviors and adapt
in real time.
3. Limitations of AI:
- Contextual judgment: AI struggles to weigh risks in a business or regulatory context.
For example, it might find a vulnerability but can’t decide if it’s truly critical to
that company’s operations.
- Creativity: Real attackers innovate — they don’t just follow known patterns. Humans excel
at thinking "outside the box" in ways AI models don’t yet replicate.
- Ethics & responsibility: Deciding how to responsibly disclose vulnerabilities or balance
customer trust is still very human.
- Adversarial risk: Attackers can manipulate AI-driven systems, feeding them misleading data
or evading detection.
4. Likely future.
Instead of replacing, AI will augment ethical hackers:
- AI will handle repetitive scanning, data analysis, and simulation.
- Hackers will focus on creative exploitation, strategy, and interpretation.
- The partnership could make assessments faster, deeper, and more accurate.
Bottom line:
AI won’t replace ethical hackers, but it will significantly change their role.
Ethical hackers of the future will need to work with AI, guiding it and applying human insight, where machines fall short.
Question #2:
I am a pentester. how can i use AI to help in my work?
Answer:
That’s a great question — AI can be a real force-multiplier in penetration testing if you know how to harness it. Here are some ways you can integrate AI into your workflow, broken down by phase of a typical engagement:
1. Reconnaissance & Information Gathering.
- OSINT automation: Use AI to parse large sets of WHOIS, Shodan, DNS, LinkedIn, or GitHub
data, quickly extracting relationships (employees, emails, exposed repos, tech stack).
- Text summarization: Feed in scraped content (press releases, job postings) and let AI
highlight likely internal systems, frameworks, or partners.
- Entity extraction: Train or prompt AI to spot emails, IPs, subdomains, or sensitive
strings from raw data dumps.
2. Scanning & Enumeration.
- Log interpretation: Paste Nmap or Nessus results and let AI group findings by
exploitability, prioritize by CVSS, or map to MITRE ATT&CK.
- Banner analysis: Feed AI strange service banners or version info; it can suggest likely
vulnerabilities, known exploits, or misconfigurations.
- Protocol fuzzing hints: AI can propose fuzzing payloads for edge-case input (common in
web apps, APIs, IoT).
3. Exploitation & Payload Crafting.
- Exploit adaptation: AI can help rewrite public PoCs to target slightly different
environments.
- Payload obfuscation ideas: Get suggestions for bypassing WAFs, IDS, or AV by altering
encodings, command structures, or macros.
- Reverse engineering aid: Summarize decompiled code, point out suspicious functions, or
hypothesize attack vectors.
4. Post-Exploitation & Reporting.
- Log analysis: Run harvested logs through AI to surface credentials, tokens, or lateral
movement opportunities.
- Privilege escalation guidance: Describe the host/system state, and AI can propose likely
misconfigurations or kernel exploits.
- Report writing: AI excels at turning raw notes into clear, professional findings with
executive summaries and technical detail (saves huge time).
5. Practical AI Uses in Daily Pentesting.
- Custom tool generation: Quickly script wrappers around APIs (Shodan, VirusTotal, Censys)
or automation for repetitive tasks.
- Cheat sheets: Ask AI for command snippets (Linux privilege escalation, PowerShell
one-liners, SQLi payloads).
- Knowledge distillation: Instead of digging through dozens of CVE writeups, AI can summarize
exploit requirements & impact.
Important note:
Always stay within legal scopes. AI can accelerate exploit generation or payload crafting, but don’t let it tempt you into going outside of your engagement boundaries.
Question #3:
Can AI analyze output of the LinPeas.sh script?
Answer:
Yes — AI can absolutely analyze the output of LinPEAS (LinPEAS.sh).
LinPEAS is a Linux privilege escalation auditing script that generates a lot of information about misconfigurations, weak permissions, vulnerable binaries, and other escalation vectors. The output is very verbose, so an AI can help by:
- Summarizing findings → Highlighting the most critical issues (e.g., SUID binaries,
writable cron jobs, weak sudo rules).
- Categorizing risks → Grouping findings by type (kernel exploits, file permissions,
network services, credentials, etc.).
- Explaining implications → For example, why a writable /etc/passwd is dangerous, or how
a misconfigured sudo rule could lead to root.
- Suggesting next steps → Recommending specific exploits or checks to attempt based on
the findings.
For example:
- If LinPEAS finds sudo -l allows running /usr/bin/vim without a password, AI could explain
that you can escalate to root via :!/bin/sh.
- If it detects a kernel version with a known exploit, AI can point you to the relevant
CVE and PoC.
If you share a snippet or full LinPEAS output here (you can redact sensitive info if needed), I can parse it and highlight the potential privilege escalation paths for you.
Do you want me to show you how I would analyze a sample LinPEAS output, or would you like to upload your script output for me to review directly?
Got it — whenever you’re ready, you can drop the LinPEAS output here, and I’ll go
through it to:
- Highlight the critical issues instead of leaving you with a giant wall of text.
- Explain what each finding means in plain language.
- Suggest possible exploitation paths (always with the caveat that you should only test
on systems you’re authorized to).
That way, instead of manually scanning hundreds of lines, you’ll get a prioritized list of "things worth looking at."
(...)
1. Can AI replace ethical hackers?
2. How pentesters can use AI to help them in their work?
3. Can AI analyze output of the LinPeas.sh script?
The 3rd question is an example, it shows how AI can be interacted with when a specific, tedious task is to be done.
AI can augment human pentesters, to hasten some of their tedious work.
AI can, for example, be used to parse and interpret output of the LinPEAS.sh script, saving pentester a lot of time and effort during the post-exploitation phase, when one tries to escalate his or her privileges.
So, humans should remain in control, be the 'pentest leaders', that use AI for help in some of their tedious tasks.
To do their work well, however, the 'pentest leaders' should know & understand the nuances of the cybersecurity fields, especially the pentesting parts. We should be aware that AI will sometimes fail, and should be able to do some things manually, when this happens.
This can be very good news for pentesters, as human pentesters who will adapt to use AI in their work will be competitive, and will remain competitive in the job market.
As the History teaches us,
During the Times of Great Changes, those who Adapt will come Victorious,
Those who Oppose Changes will be left behind.
--
Important: Before using AI during the Real-Life Pentest (as opposed to Capture the Flag exercises on some hacking sites like the Hack the Box or Try Hack Me), check with lawyer if it's legal, if it's not violation of NDA or contract signed with customer.
Can AI Replace Ethical Hackers?
Answer:
That’s a deep question. Let’s break it down:
Ethical hackers (or penetration testers) simulate cyberattacks on systems to uncover vulnerabilities before malicious actors exploit them. Their role isn’t just technical — it also involves:
- Understanding business contexts and risks,
- Thinking creatively and unpredictably, like an attacker would.
- Communicating findings clearly to stakeholders.
- Advising on remediation strategies and balancing security with usability.
2. What AI can do today?
AI is already being applied in security testing and operations:
- Automation: AI can scan for known vulnerabilities, misconfigurations, and patterns at scale
much faster than humans.
- Exploit simulation: Some AI systems can chain together attack paths or fuzz inputs to find
weaknesses.
- Threat intelligence: AI can analyze vast amounts of threat data, flag anomalies, and
predict possible attack vectors.
- Red teaming tools: Emerging AI-driven platforms can mimic attacker behaviors and adapt
in real time.
3. Limitations of AI:
- Contextual judgment: AI struggles to weigh risks in a business or regulatory context.
For example, it might find a vulnerability but can’t decide if it’s truly critical to
that company’s operations.
- Creativity: Real attackers innovate — they don’t just follow known patterns. Humans excel
at thinking "outside the box" in ways AI models don’t yet replicate.
- Ethics & responsibility: Deciding how to responsibly disclose vulnerabilities or balance
customer trust is still very human.
- Adversarial risk: Attackers can manipulate AI-driven systems, feeding them misleading data
or evading detection.
4. Likely future.
Instead of replacing, AI will augment ethical hackers:
- AI will handle repetitive scanning, data analysis, and simulation.
- Hackers will focus on creative exploitation, strategy, and interpretation.
- The partnership could make assessments faster, deeper, and more accurate.
Bottom line:
AI won’t replace ethical hackers, but it will significantly change their role.
Ethical hackers of the future will need to work with AI, guiding it and applying human insight, where machines fall short.
I am a pentester. how can i use AI to help in my work?
Answer:
That’s a great question — AI can be a real force-multiplier in penetration testing if you know how to harness it. Here are some ways you can integrate AI into your workflow, broken down by phase of a typical engagement:
- OSINT automation: Use AI to parse large sets of WHOIS, Shodan, DNS, LinkedIn, or GitHub
data, quickly extracting relationships (employees, emails, exposed repos, tech stack).
- Text summarization: Feed in scraped content (press releases, job postings) and let AI
highlight likely internal systems, frameworks, or partners.
- Entity extraction: Train or prompt AI to spot emails, IPs, subdomains, or sensitive
strings from raw data dumps.
2. Scanning & Enumeration.
- Log interpretation: Paste Nmap or Nessus results and let AI group findings by
exploitability, prioritize by CVSS, or map to MITRE ATT&CK.
- Banner analysis: Feed AI strange service banners or version info; it can suggest likely
vulnerabilities, known exploits, or misconfigurations.
- Protocol fuzzing hints: AI can propose fuzzing payloads for edge-case input (common in
web apps, APIs, IoT).
3. Exploitation & Payload Crafting.
- Exploit adaptation: AI can help rewrite public PoCs to target slightly different
environments.
- Payload obfuscation ideas: Get suggestions for bypassing WAFs, IDS, or AV by altering
encodings, command structures, or macros.
- Reverse engineering aid: Summarize decompiled code, point out suspicious functions, or
hypothesize attack vectors.
4. Post-Exploitation & Reporting.
- Log analysis: Run harvested logs through AI to surface credentials, tokens, or lateral
movement opportunities.
- Privilege escalation guidance: Describe the host/system state, and AI can propose likely
misconfigurations or kernel exploits.
- Report writing: AI excels at turning raw notes into clear, professional findings with
executive summaries and technical detail (saves huge time).
5. Practical AI Uses in Daily Pentesting.
- Custom tool generation: Quickly script wrappers around APIs (Shodan, VirusTotal, Censys)
or automation for repetitive tasks.
- Cheat sheets: Ask AI for command snippets (Linux privilege escalation, PowerShell
one-liners, SQLi payloads).
- Knowledge distillation: Instead of digging through dozens of CVE writeups, AI can summarize
exploit requirements & impact.
Important note:
Always stay within legal scopes. AI can accelerate exploit generation or payload crafting, but don’t let it tempt you into going outside of your engagement boundaries.
Can AI analyze output of the LinPeas.sh script?
Answer:
Yes — AI can absolutely analyze the output of LinPEAS (LinPEAS.sh).
- Summarizing findings → Highlighting the most critical issues (e.g., SUID binaries,
writable cron jobs, weak sudo rules).
- Categorizing risks → Grouping findings by type (kernel exploits, file permissions,
network services, credentials, etc.).
- Explaining implications → For example, why a writable /etc/passwd is dangerous, or how
a misconfigured sudo rule could lead to root.
- Suggesting next steps → Recommending specific exploits or checks to attempt based on
the findings.
For example:
- If LinPEAS finds sudo -l allows running /usr/bin/vim without a password, AI could explain
that you can escalate to root via :!/bin/sh.
- If it detects a kernel version with a known exploit, AI can point you to the relevant
CVE and PoC.
If you share a snippet or full LinPEAS output here (you can redact sensitive info if needed), I can parse it and highlight the potential privilege escalation paths for you.
Do you want me to show you how I would analyze a sample LinPEAS output, or would you like to upload your script output for me to review directly?
[ my answer ]: not for now, but in future - probably yes.
Got it — whenever you’re ready, you can drop the LinPEAS output here, and I’ll go
through it to:
- Highlight the critical issues instead of leaving you with a giant wall of text.
- Explain what each finding means in plain language.
- Suggest possible exploitation paths (always with the caveat that you should only test
on systems you’re authorized to).
That way, instead of manually scanning hundreds of lines, you’ll get a prioritized list of "things worth looking at."
(...)
Tuesday, 4 February 2025
Cyber Security Course's Reference (Offensive Security/Pentesting).
There are many roles in the Cybersecurity job market. One of these is Ethical Hacking, also known as 'Offensive Security', 'Red Teaming', or as 'Pentesting' ('Penetration Testing').
I've enlisted myself for two Pentesting courses:
- Cyberium (started in December 2024),
- Hack The Box (started in August 2025).
Making reference notes as I progress.
These notes won't replace the full courses, but may prove to be useful for myself and others still - if only as a reference.
--
List of lessons:
1. Kali Linux Reference for Pentesters,
2. Foundations of Cyber Security,
3. Introduction to Pentesting,
4. Pentesting: Art of Reconaissance,
5. Pentesting: Scanning & Enumeration,
6. Pentesting: Vulnerability Analysis,
7. Pentesting: Manual Exploitation of Systems, Services & Applications,
8. Pentesting: Metasploit in Practice,
9. Pentesting: Attacks on Web Applications,
10. Pentesting: Documentation & Reporting,
11. Pentesting: Post-Exploitation,
12. Pentesting: Cloud Security / work in progress /,
13. Pentesting: Attacks on Active Directory / to be done /,
... and the final chapter, created by this blog's author.
14. Martial Arts Philosophy in Hacking.
See also, if You wish:
> [ Artificial Intelligence & Ethical Hacking ].
--
I've completed one of the courses (Cyberium), and got two certificates (one for completing the course, and one for final exam). The most important one is for succesfully passing the final exam:
But as this blog's author sees it, it's only beginning of the True Training (like Black Belt in Martial Arts, where the Mastery of Basics in just a good start).
I plan to develop myself in Ethical Hacking for the whole rest of my life. There's so much to do, I think I won't lack topics to pursue.
I want to combine Hacking with Programming, Artificial Intelligence and Quantum Informatics too.
Perhaps I'll need to do some Advanced Mathematics, including:
- Predicate Calculus, First Order Logic & Higher Order Logic,
(for Artificial Intelligence mostly)
- Numerical Methods,
(only course that I failed when I was studying Informatics on Warsaw University, MIMUW)
- Calculus (also known as Mathematical Analysis),
(somehow I succesfully passed this course on MIMUW, but in fact I have some irrational mental
problems, making me fail every time when I want to learn about Integrals. :(. I just know that
Definite Integral can be seen as Area Under the Curve, and that Indefinite Integrals are about
finding Antiderivative of a function)
- Cryptography & Post-Quantum Cryptography.
(for Ethical Hacking mostly)
... but still, not sure how I'll do it, and if I'll have time for that.
But then, even Einstein had problems with Mathematics.
I don't want my problems with Mathematics stop my development in Hacking and Sciences.
Maybe someday I can 'reforge' my weaknesses into strengths.
I've enlisted myself for two Pentesting courses:
- Cyberium (started in December 2024),
- Hack The Box (started in August 2025).
Making reference notes as I progress.
These notes won't replace the full courses, but may prove to be useful for myself and others still - if only as a reference.
--
List of lessons:
1. Kali Linux Reference for Pentesters,
2. Foundations of Cyber Security,
3. Introduction to Pentesting,
4. Pentesting: Art of Reconaissance,
5. Pentesting: Scanning & Enumeration,
6. Pentesting: Vulnerability Analysis,
7. Pentesting: Manual Exploitation of Systems, Services & Applications,
8. Pentesting: Metasploit in Practice,
9. Pentesting: Attacks on Web Applications,
10. Pentesting: Documentation & Reporting,
11. Pentesting: Post-Exploitation,
12. Pentesting: Cloud Security / work in progress /,
13. Pentesting: Attacks on Active Directory / to be done /,
... and the final chapter, created by this blog's author.
14. Martial Arts Philosophy in Hacking.
See also, if You wish:
> [ Artificial Intelligence & Ethical Hacking ].
--
I've completed one of the courses (Cyberium), and got two certificates (one for completing the course, and one for final exam). The most important one is for succesfully passing the final exam:
But as this blog's author sees it, it's only beginning of the True Training (like Black Belt in Martial Arts, where the Mastery of Basics in just a good start).
I plan to develop myself in Ethical Hacking for the whole rest of my life. There's so much to do, I think I won't lack topics to pursue.
I want to combine Hacking with Programming, Artificial Intelligence and Quantum Informatics too.
Perhaps I'll need to do some Advanced Mathematics, including:
- Predicate Calculus, First Order Logic & Higher Order Logic,
(for Artificial Intelligence mostly)
- Numerical Methods,
(only course that I failed when I was studying Informatics on Warsaw University, MIMUW)
- Calculus (also known as Mathematical Analysis),
(somehow I succesfully passed this course on MIMUW, but in fact I have some irrational mental
problems, making me fail every time when I want to learn about Integrals. :(. I just know that
Definite Integral can be seen as Area Under the Curve, and that Indefinite Integrals are about
finding Antiderivative of a function)
- Cryptography & Post-Quantum Cryptography.
(for Ethical Hacking mostly)
... but still, not sure how I'll do it, and if I'll have time for that.
But then, even Einstein had problems with Mathematics.
I don't want my problems with Mathematics stop my development in Hacking and Sciences.
Maybe someday I can 'reforge' my weaknesses into strengths.
Sunday, 1 September 2024
Computers, Memory Pyramid & Code Size Optimization.
What is a Computer?
In Computer Sciences, Computer - by definition - is processor with memory and input/output devices. Any electronic device that has these is considered Computer. This includes Smartphones and many other tools.
Memory, Persistent or Transient.
There are two types of memory / pl: 'Są dwa rodzaje pamięci' /:
- Persistent / pl: 'Trwała' /,
- Transient / pl: 'Ulotna' /.
Persistent objects are those which continue to exist even after the program that created them has stopped running.
Transient objects cease to exist when program that created them stops.
Pyramid of Needs.
There are many types of memory, differing in price and speed of access.
Starting from the most expensive but fastest, there are:
- processor's registers,
- layers of the processor's cache (L1-L3, for example),
- RAM (Random Access Memory),
- persistent SSD/HDD storage.
Code Size optimization.
Smaller programs can be very quick in their execution.
When the whole program fits - for example - in L2 Processor's Cache, there's no need to reach RAM via BUS, so the code runs very quickly - as it's closer to the processor than RAM.
What if a Program doesn't fit in Transient Memory?
When a program needs to be executed, it needs to be loaded into the transient memory first.
However, Modern Operating Systems can send currently unused Program's parts & other Resources / for example: graphics image files, sound files and/or text files / from Transient Memory to Persistent SDD/HDD Memory and retrieve other Resources/Part(s) from Persistent Memory to Transient Memory / Usually from disk to RAM /.
/ pl: 'Współczesne Systemy Operacyjne mogą wysłać aktualnie niewykorzystywane części Oprogramowania i innych zasobów na dysk... i sprowadzić inne zasoby/części z pamięci trwałej do ulotnej, najczęściej do pamięci RAM' /.
Let's note, however, that loading/storing data in persistent memory is much slower than loading/storing from/to Transient RAM.
This is an automated operation in Modern Operating Systems, so programmers do not need to worry so much about that. Computers just slow down sometimes - and SSD/HDD becomes quite busy, when doing that.
This sometimes causes 'Flickering' / pl: 'Migotanie', 'Szamotanie' /, however. Code & Data is loaded/unloaded from/to persistent memory too slowly and can cause a Computer System to slow down or crash, as the Computing Resources run out. / Mostly CPU usage & Memory usage /.
So - in theory at least - a Computer can try to run larger programs than Computer has RAM.
Often it fails, but in theory this can work well.
In Computer Sciences, Computer - by definition - is processor with memory and input/output devices. Any electronic device that has these is considered Computer. This includes Smartphones and many other tools.
Memory, Persistent or Transient.
There are two types of memory / pl: 'Są dwa rodzaje pamięci' /:
- Persistent / pl: 'Trwała' /,
- Transient / pl: 'Ulotna' /.
Persistent objects are those which continue to exist even after the program that created them has stopped running.
Transient objects cease to exist when program that created them stops.
Pyramid of Needs.
There are many types of memory, differing in price and speed of access.
Starting from the most expensive but fastest, there are:
- processor's registers,
- layers of the processor's cache (L1-L3, for example),
- RAM (Random Access Memory),
- persistent SSD/HDD storage.
Code Size optimization.
Smaller programs can be very quick in their execution.
When the whole program fits - for example - in L2 Processor's Cache, there's no need to reach RAM via BUS, so the code runs very quickly - as it's closer to the processor than RAM.
What if a Program doesn't fit in Transient Memory?
When a program needs to be executed, it needs to be loaded into the transient memory first.
However, Modern Operating Systems can send currently unused Program's parts & other Resources / for example: graphics image files, sound files and/or text files / from Transient Memory to Persistent SDD/HDD Memory and retrieve other Resources/Part(s) from Persistent Memory to Transient Memory / Usually from disk to RAM /.
/ pl: 'Współczesne Systemy Operacyjne mogą wysłać aktualnie niewykorzystywane części Oprogramowania i innych zasobów na dysk... i sprowadzić inne zasoby/części z pamięci trwałej do ulotnej, najczęściej do pamięci RAM' /.
Let's note, however, that loading/storing data in persistent memory is much slower than loading/storing from/to Transient RAM.
This is an automated operation in Modern Operating Systems, so programmers do not need to worry so much about that. Computers just slow down sometimes - and SSD/HDD becomes quite busy, when doing that.
This sometimes causes 'Flickering' / pl: 'Migotanie', 'Szamotanie' /, however. Code & Data is loaded/unloaded from/to persistent memory too slowly and can cause a Computer System to slow down or crash, as the Computing Resources run out. / Mostly CPU usage & Memory usage /.
So - in theory at least - a Computer can try to run larger programs than Computer has RAM.
Often it fails, but in theory this can work well.
Monday, 29 April 2024
Logic & Axioms.
There are many Logics, based on different Axioms.
/ EN: 'Axiom' = PL: 'Aksjomat' /.
Axioms are statements that are not proven, but assumed as true, taken on faith.
/ EN: 'assumption' = PL: 'założenie' /.
Depending on the Axioms used, Theorems can be proven or disproven, and the whole Mathematical & Logical Apparatus can be developed.
Basing on Boolean Algebra, double negation evaluates to confirmation, but in some languages - polish for example - double negation does not mean confirmation, it does mean emphasis on negation, giving negation more power.
There are rules for negating Quantifiers as well.
/ EN: 'negation' = PL: 'zaprzeczenie' /,
/ EN: 'confirmation' = PL: 'potwierdzenie' /,
/ EN: 'emphasis' = PL: 'nacisk' /,
/ EN: 'quantifier' = PL: 'kwantyfikator' /.
/ według Algebry Boole'a i Teorii Kwantyfikatorów wylicza się do:
'istnieje taki moment w czasie kiedy zgodzę się na te warunki'. /
/ a w mowie potocznej znaczy: 'nie istnieje taki moment w czasie kiedy zgodzę się na te warunki'. /
Therefore, Speech of the Art, Literature, can have the Logic based on different Axioms than Boolean Algebra.
We can say that: 'Life is more than Boolean Algebra and Quantifiers' when we want to use casual, non-logical talks.
When Boolean Algebra and Quantifiers are useful then? It's useful in computer programming, or when we want to talk logically and precisely, or when we want to express our wishes logically and precisely. But when we opt for logical and precise speech, let's make sure first that other people we talk with understand our logic.
We can also define the addition operation / it's an Axiom too / differently as well.
We can have an exception:
1+1 = 2, 1+2 = 3, 2+1 = 3, 1+3 = 4, 3+1 = 4, 2+2 = 5, 1+4 = 5, 4+1 = 5, 2+3 = 5, 3+2 = 5, 1+5 = 6, 5+1 = 6, 2+4 = 6, ...
We can also redefine the addition operation differently on the more general, more universal scale:
n+2 in our redefined addition operation is n+2+1 in classical addition operation.
By doing so, by changing Axioms, we just have revolutionized the Mathematics. ;)
Many different theorems apply now, but at least we know that we can make expression 2+2 = 5 to be evaluated as true in a certain Context - even if this brings more or less desired effects in process ;).
We are free to assume any Axioms we want, examples can be multiplied infinitely.
Which Logic is 'better' than other, then?
... it depends on the assumed Criteria, which might be Axioms as well.
Tuesday, 6 February 2024
The Enigma Cipher of WW2 & the Turing Machine.
Polish and British mathematicians were among the best of people who cracked the Adolph Hitler's cipher named Enigma, it happened during the World War 2nd.
Enigma breaking was hard, and the mathematicians were hunted by Germany's spies.
Enigma evolved, so parts of the cipher were to be cracked again and again. It was not about making automation once, and letting it work for the rest of WW2 ... but statistically it worked so the effort was continued.
Doing maths when time flew and lives were at stake.... so stressful. The Germany's spies added to the dangers & to the stress too.
Polish mathematicians had one of few of first computers ... it was nicknamed: 'Bomb', for it was so big invention. It increased efficiency of the enigma cipher cracking.
--
Sources:
1. 'Cubits & Shrodinger's Cat. From Turing Machine to Quantum Computers' by John Gribbin.
(Polish Edition).
2. The internet (wikipedia & the ważniak mostly) and my own thinking.
Enigma breaking was hard, and the mathematicians were hunted by Germany's spies.
Enigma evolved, so parts of the cipher were to be cracked again and again. It was not about making automation once, and letting it work for the rest of WW2 ... but statistically it worked so the effort was continued.
Doing maths when time flew and lives were at stake.... so stressful. The Germany's spies added to the dangers & to the stress too.
Polish mathematicians had one of few of first computers ... it was nicknamed: 'Bomb', for it was so big invention. It increased efficiency of the enigma cipher cracking.
--
Sources:
1. 'Cubits & Shrodinger's Cat. From Turing Machine to Quantum Computers' by John Gribbin.
(Polish Edition).
2. The internet (wikipedia & the ważniak mostly) and my own thinking.
Friday, 24 March 2023
Realtime Systems.
Introduction.
Real-Time systems are computer systems in which succesful task performance depends on two factors:
- succesful result of computation,
- exact deadline time in which task was performed.
When a task execution time exceeds it's time deadline, we can say that system failed.
Hard, Firm & Soft Real-time Systems.
In the 'Hard Real-time Systems' missing a deadline is a total system failure. Hard realtime systems are created when missing a deadline can result in hardware damage or costs lives or health.
In 'Firm Real-time Systems' infrequent deadline misses are tolerable, but may degrade the system's quality of service. The usefulness of a result is zero after its deadline, but no damage or personnel loss occurs.
In 'Soft Real-time Systems' the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.
Requirements.
For a computer system to meet criteria of the 'Hard Real-time System', requirements are:
- well understood & fast enough hardware,
- real-time operating system (for example: RTLinux),
- every software piece must adhere to the 'hard real-time requirements'; software must generate results in the deadline time.
Real-Time systems are computer systems in which succesful task performance depends on two factors:
- succesful result of computation,
- exact deadline time in which task was performed.
When a task execution time exceeds it's time deadline, we can say that system failed.
Hard, Firm & Soft Real-time Systems.
In the 'Hard Real-time Systems' missing a deadline is a total system failure. Hard realtime systems are created when missing a deadline can result in hardware damage or costs lives or health.
In 'Firm Real-time Systems' infrequent deadline misses are tolerable, but may degrade the system's quality of service. The usefulness of a result is zero after its deadline, but no damage or personnel loss occurs.
In 'Soft Real-time Systems' the usefulness of a result degrades after its deadline, thereby degrading the system's quality of service.
Requirements.
For a computer system to meet criteria of the 'Hard Real-time System', requirements are:
- well understood & fast enough hardware,
- real-time operating system (for example: RTLinux),
- every software piece must adhere to the 'hard real-time requirements'; software must generate results in the deadline time.
Classic Concurrency Problems.
1. Mutual Exclusion.
Let's assume that two processess want to access critical section of code. They are acting as such:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Critical section is this program fragment, that can be executed by at most one process at once.
We assume that each process which enters critical section, will leave it in finite time.
See also: Petersen's Algorithm.
2. Producers & Consumers.
There are P>0 processes in system, which produce certain data, and K>0 processes which receive data from producers. Between producers and consumers there can be buffer with capacity B, whose task is balancing temporary differences during processes execution time. Processes that produce data we'll call producers, and processes receiving data --- consumers. Task is about synchronizing work of producers and consumers, such as that:
* Consumer would wait for data receive in situation when buffer is empty.
* Producer, when putting data in buffer would not overwrite data already written, but not received yet by consumer. It requires stopping temporarily producer in situation when there is no empty space in buffer.
* If many consumers wait for when data arrives in buffer, and if constantly new data is produced, then each waiting consumer will get something from buffer.
* Won't happen such situation, that certain consumer will wait infinitely for getting data, if data arrives in buffer constantly.
* If many producers wait for buffer's free space, and consumers constantly get something from buffer, then each of waiting producers will be able to put something into buffer. There won't happen situation such as certain producer will wait infinitely, if constantly something is taken from buffer.
There are variants to this problem:
* Buffer might be infinite.
* Cyclic buffer with finite space.
* No buffer at all.
* Many producers or only one.
* Many consumers or only one.
* Data might be produced and consumed at quicker rate (more than one unit at once).
* Data has to be read in writing order, or not.
Producers and consumers problem is abstraction of many situations existing in computer systems, for example: keyboard data write to buffer by keyboard device driver, and it's read by operating system.
3. Readers and Writers.
There are C>0 processes working in system. They read certain data. There are P>0 processes which write data. Processes writing data we'll call writers, processes reading data --- readers. Moment when processes have access to data, we'll call 'reading room visit' or 'reading room stay'.
Let's notice that many processes can read data at once. If someone wants to modify that data, then it's reasonable to block access to this data for all other processes for the time of read. It prevents read of inconsistent data (for example, partially modified data). Overall schema for processes work is such:
process Reader;
begin
repeat
personal_affairs;
begining_reader_protocol;
READ;
ending_reader_protocol;
until false
end
process Writer;
begin
repeat
personal_affairs;
begining_writer_protocol;
WRITE;
ending_writer_protocol;
until false
end
Beginning and ending protocols of selected processes should be written in a way, that allows for these conditions to be met:
* Many readers should have simultaneous access to reading room.
* If in reading room there's writer, then no one else does not write or read.
* Each reader, which wishes for data read, at some point will read them.
* Each writer, which wishes for data modification, at some point will write such modifications.
There are variants to this problem:
* In reading room many readers can spend their time at once.
* Reading room may have limited capacity.
* Writers may have priority over readers (but then we'll resign from readers liveness).
* Readers may have priority over writers (but then we'll resign from writers liveness).
4. Five Philosophers.
This problem does not have practical analogies, unlike previous classic problems, but it very well illustrates problems happening when concurrent programs are made.
Five philosophers dine by round table. Before each there's plate. Between plates lie forks. In middle of the table there's serving dish with fish. Each philosopher thinks. When he gets hungry, he reaches for forks laying at his right and left side, then starts eating. When he's done eating, he puts forks away and again devotes himself to thinking.
Scheme of such philospoher is such then:
process Philospher (i: 0..4);
begin
repeat
think;
beginning_protocol;
eating;
ending_protocol;
until false
end;
Task is to write beginning and ending protocols, such as following conditions would be met:
* Only one philospoher ate with the same fork at the same time.
* Each of the philosophers ate only and always with two (and always those which lay near his plate) forks.
* No philosopher would die of starvation.
* Also we want that each of the philosophers would act the same way.
Solution to this riddle is to use waiter to let only four philosophers at the dining table at the same time, and let fifth wait. When philosopher is done eating, he leaves table and joins queue and can only return to table when waiter allows him to do this.
See also, if You wish: Basics of Concurrent Programming.
Let's assume that two processess want to access critical section of code. They are acting as such:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Critical section is this program fragment, that can be executed by at most one process at once.
We assume that each process which enters critical section, will leave it in finite time.
See also: Petersen's Algorithm.
2. Producers & Consumers.
There are P>0 processes in system, which produce certain data, and K>0 processes which receive data from producers. Between producers and consumers there can be buffer with capacity B, whose task is balancing temporary differences during processes execution time. Processes that produce data we'll call producers, and processes receiving data --- consumers. Task is about synchronizing work of producers and consumers, such as that:
* Consumer would wait for data receive in situation when buffer is empty.
* Producer, when putting data in buffer would not overwrite data already written, but not received yet by consumer. It requires stopping temporarily producer in situation when there is no empty space in buffer.
* If many consumers wait for when data arrives in buffer, and if constantly new data is produced, then each waiting consumer will get something from buffer.
* Won't happen such situation, that certain consumer will wait infinitely for getting data, if data arrives in buffer constantly.
* If many producers wait for buffer's free space, and consumers constantly get something from buffer, then each of waiting producers will be able to put something into buffer. There won't happen situation such as certain producer will wait infinitely, if constantly something is taken from buffer.
There are variants to this problem:
* Buffer might be infinite.
* Cyclic buffer with finite space.
* No buffer at all.
* Many producers or only one.
* Many consumers or only one.
* Data might be produced and consumed at quicker rate (more than one unit at once).
* Data has to be read in writing order, or not.
Producers and consumers problem is abstraction of many situations existing in computer systems, for example: keyboard data write to buffer by keyboard device driver, and it's read by operating system.
3. Readers and Writers.
There are C>0 processes working in system. They read certain data. There are P>0 processes which write data. Processes writing data we'll call writers, processes reading data --- readers. Moment when processes have access to data, we'll call 'reading room visit' or 'reading room stay'.
Let's notice that many processes can read data at once. If someone wants to modify that data, then it's reasonable to block access to this data for all other processes for the time of read. It prevents read of inconsistent data (for example, partially modified data). Overall schema for processes work is such:
process Reader;
begin
repeat
personal_affairs;
begining_reader_protocol;
READ;
ending_reader_protocol;
until false
end
process Writer;
begin
repeat
personal_affairs;
begining_writer_protocol;
WRITE;
ending_writer_protocol;
until false
end
Beginning and ending protocols of selected processes should be written in a way, that allows for these conditions to be met:
* Many readers should have simultaneous access to reading room.
* If in reading room there's writer, then no one else does not write or read.
* Each reader, which wishes for data read, at some point will read them.
* Each writer, which wishes for data modification, at some point will write such modifications.
There are variants to this problem:
* In reading room many readers can spend their time at once.
* Reading room may have limited capacity.
* Writers may have priority over readers (but then we'll resign from readers liveness).
* Readers may have priority over writers (but then we'll resign from writers liveness).
4. Five Philosophers.
This problem does not have practical analogies, unlike previous classic problems, but it very well illustrates problems happening when concurrent programs are made.
Five philosophers dine by round table. Before each there's plate. Between plates lie forks. In middle of the table there's serving dish with fish. Each philosopher thinks. When he gets hungry, he reaches for forks laying at his right and left side, then starts eating. When he's done eating, he puts forks away and again devotes himself to thinking.
Scheme of such philospoher is such then:
process Philospher (i: 0..4);
begin
repeat
think;
beginning_protocol;
eating;
ending_protocol;
until false
end;
Task is to write beginning and ending protocols, such as following conditions would be met:
* Only one philospoher ate with the same fork at the same time.
* Each of the philosophers ate only and always with two (and always those which lay near his plate) forks.
* No philosopher would die of starvation.
* Also we want that each of the philosophers would act the same way.
Solution to this riddle is to use waiter to let only four philosophers at the dining table at the same time, and let fifth wait. When philosopher is done eating, he leaves table and joins queue and can only return to table when waiter allows him to do this.
See also, if You wish: Basics of Concurrent Programming.
Petersen's Algorithm.
It's solution to problem of synchronizing two processess (running programs) wanting to enter critical section of code (section that cannot be accessed by more than one process at the same time).
Using global variables (that indicate which process[-es] want to enter critical section, and which process waits) and simple programming instructions we can ensure that only one process enters critical section at given time.
Pseudocode:
var
process1wants: boolean := false;
process2wants: boolean := false;
whoWaits: 1..2 := 1;
process P1;
begin
while true do
begin
personalAffairs;
process1wants := true;
who_waits := 1;
while process2wants and (whoWaits = 1) do {nothing};
criticalSection;
process1wants := false;
end
end;
process P2;
begin
while true do
begin
personalAffairs;
process2wants := true;
who_waits := 2;
while process1wants and (whoWaits = 2) do
criticalSection;
process2wants := false;
end
end;
Using global variables (that indicate which process[-es] want to enter critical section, and which process waits) and simple programming instructions we can ensure that only one process enters critical section at given time.
Pseudocode:
var
process1wants: boolean := false;
process2wants: boolean := false;
whoWaits: 1..2 := 1;
process P1;
begin
while true do
begin
personalAffairs;
process1wants := true;
who_waits := 1;
while process2wants and (whoWaits = 1) do {nothing};
criticalSection;
process1wants := false;
end
end;
process P2;
begin
while true do
begin
personalAffairs;
process2wants := true;
who_waits := 2;
while process1wants and (whoWaits = 2) do
criticalSection;
process2wants := false;
end
end;
Basics of Concurrent Programming.
Concurrent work is multiple works happening at the same time, processor time quants are divided among many processes.
Process is a running program.
Thread (lightweigh process, LWP) is object inside heavyweight process that has it's own control & that shares resources with other threads in the same process.
Critical Section.
Critical section is a code section that can be accessed by only one process or thread at the same time.
Critical section has uses for example in banking: we do not want data to be overwritten as it's written by other process, or read during writing.
Example pseudocode:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Readers & Writers.
In computer science, the readers-writers problem is an example of a common computing problem in concurrency.
Shared resource is abstracted as a Reading Room.
More than one Reader may be in a Reading Room, but if writer is in a Reading Room - no one else can be there.
An example algorithm for handling the readers-writers problem is as follows:
Reader's beginning protocol:
reader waits (goes asleep), if there's writer in a reading room.
Writer's beginning protocol:
writer waits (goes asleep), if there's someone in a reading room.
Reader's end protocol:
if is last exitting person, then awakens & lets writer in - if writer waits.
Writer's end protocol:
if readers wait, then awakens them all, otherwise, if writer waits, awakens one.
There should be a limit on maximum number of readers let in in a reading room, when writer(s) is/are awaiting.
See also: Petersen's Algorithm, Classic Concurrency Problems.
Process is a running program.
Thread (lightweigh process, LWP) is object inside heavyweight process that has it's own control & that shares resources with other threads in the same process.
Critical Section.
Critical section is a code section that can be accessed by only one process or thread at the same time.
Critical section has uses for example in banking: we do not want data to be overwritten as it's written by other process, or read during writing.
Example pseudocode:
process P;
begin
while true do
begin
personal_affairs;
begining_protocol;
critical_section;
ending_protocol;
end
end;
Readers & Writers.
In computer science, the readers-writers problem is an example of a common computing problem in concurrency.
Shared resource is abstracted as a Reading Room.
More than one Reader may be in a Reading Room, but if writer is in a Reading Room - no one else can be there.
An example algorithm for handling the readers-writers problem is as follows:
Reader's beginning protocol:
reader waits (goes asleep), if there's writer in a reading room.
Writer's beginning protocol:
writer waits (goes asleep), if there's someone in a reading room.
Reader's end protocol:
if is last exitting person, then awakens & lets writer in - if writer waits.
Writer's end protocol:
if readers wait, then awakens them all, otherwise, if writer waits, awakens one.
There should be a limit on maximum number of readers let in in a reading room, when writer(s) is/are awaiting.
See also: Petersen's Algorithm, Classic Concurrency Problems.
Saturday, 21 January 2023
Automated Tests.
Application Design & Use Cases.
Often, when a customer orders application, she or he orders a collection of a certain functionalities.
For example:
- logging into online email application,
- deleting all spam in spam inbox,
- logging off automatically after a given time,
- configuring email sorting preferences,
- ...
Use cases are means of specifying these functionalities, defined by a number of steps (click here, scroll here, type something here, read report's field #n, etc ...).
A minimal set of use cases often determines how user interface should look, is often a formal requirement for ordered application functionalities - can be a part of the business contract between a customer & a developer company.
Automated Tests, Changes & Debugging.
Often tests for use cases can be automated, can be performed after any change is introduced into the code ... just before program's compilation, just before running an application, or at any other convenient moment.
By using Automated Use Case Tests, programmers can be comfortable that when they (or their teammates) change parts of the code, the older parts of the code (previous functionalities) that they are responsible for - won't prove erroneous after the new code additions.
Automated Use Case tests often show when part of the code is erroneous after changes, and while these are far from being 'proofs of code's correctness', these are extremely practical nevertheless. Even if not every error is caught by these - carefully designed tests can quickly find basic functionality failures. Other errors can still be found & fixed using other methods, and it's still easier to fix one error than multiple overlapping ones.
More than that - carefully designed automated tests can help programmer to create 'Mental Test Harness' that let's them more boldly & quickly do larger changes in code without inspecting the same things over & over, without fearing of application breakages so much.
This also builds Trust & Responsibility in the teams - with tests it's quick & easy to find out when someone breaks other teammate's code parts - at early stage of failure at that, so it can be addressed before error turns to be too complex to address quickly, before true stress, psychological dramas & employee firings start, before project's budgets & time schedules are endangered.
In many ways, Automated Tests help to develop applications with much more of the speed & security, with only a small amount of extra code at start (tests have to be designed & written too) & with a small amount of maintenance (when requirements change, tests have to be modified).
Documentation & Automated Tests.
Important aspect of code's quality are automated tests and documentation.
Developers should not write in documentation anything they please, there should be formal standards on what to write and how.
Class documentation should state the Contract between class user and class creator - class responsibility, invariants, what results code provides on which conditions. Results are not only returned values of methods, but also exceptions thrown, state changes, methods called and events raised.
As of how classes should be documented - there's for example Javadoc writing guidelines and requirements, these are about style, keywords and syntax.
Automated Tests for each of classes should be grouped in a single file.
Within that file many tests can be provided, one or more tests for each of tested class' methods.
Tests should check if documented contracts are intact, should check every of 'border criteria'.
Tests can also be written for software's use cases.
... for Java's automated testing tools, check, if You wish:
- JUnit 5,
- EasyMock.
See also: Software Development & Quality.
Often, when a customer orders application, she or he orders a collection of a certain functionalities.
For example:
- logging into online email application,
- deleting all spam in spam inbox,
- logging off automatically after a given time,
- configuring email sorting preferences,
- ...
Use cases are means of specifying these functionalities, defined by a number of steps (click here, scroll here, type something here, read report's field #n, etc ...).
A minimal set of use cases often determines how user interface should look, is often a formal requirement for ordered application functionalities - can be a part of the business contract between a customer & a developer company.
Automated Tests, Changes & Debugging.
Often tests for use cases can be automated, can be performed after any change is introduced into the code ... just before program's compilation, just before running an application, or at any other convenient moment.
By using Automated Use Case Tests, programmers can be comfortable that when they (or their teammates) change parts of the code, the older parts of the code (previous functionalities) that they are responsible for - won't prove erroneous after the new code additions.
Automated Use Case tests often show when part of the code is erroneous after changes, and while these are far from being 'proofs of code's correctness', these are extremely practical nevertheless. Even if not every error is caught by these - carefully designed tests can quickly find basic functionality failures. Other errors can still be found & fixed using other methods, and it's still easier to fix one error than multiple overlapping ones.
More than that - carefully designed automated tests can help programmer to create 'Mental Test Harness' that let's them more boldly & quickly do larger changes in code without inspecting the same things over & over, without fearing of application breakages so much.
This also builds Trust & Responsibility in the teams - with tests it's quick & easy to find out when someone breaks other teammate's code parts - at early stage of failure at that, so it can be addressed before error turns to be too complex to address quickly, before true stress, psychological dramas & employee firings start, before project's budgets & time schedules are endangered.
In many ways, Automated Tests help to develop applications with much more of the speed & security, with only a small amount of extra code at start (tests have to be designed & written too) & with a small amount of maintenance (when requirements change, tests have to be modified).
Documentation & Automated Tests.
Important aspect of code's quality are automated tests and documentation.
Developers should not write in documentation anything they please, there should be formal standards on what to write and how.
Class documentation should state the Contract between class user and class creator - class responsibility, invariants, what results code provides on which conditions. Results are not only returned values of methods, but also exceptions thrown, state changes, methods called and events raised.
As of how classes should be documented - there's for example Javadoc writing guidelines and requirements, these are about style, keywords and syntax.
Automated Tests for each of classes should be grouped in a single file.
Within that file many tests can be provided, one or more tests for each of tested class' methods.
Tests should check if documented contracts are intact, should check every of 'border criteria'.
Tests can also be written for software's use cases.
... for Java's automated testing tools, check, if You wish:
- JUnit 5,
- EasyMock.
See also: Software Development & Quality.
Contracts.
Introduction.
Design by Contract is the Software Collaboration Method.
Contract / between class user and class author / should state under which condition class will provide it's services to class user, and what these services are.
Contract.
There are Preconditions, Postconditions and Invariants that regulate contract.
Precondition is a condition that is required for something to happen. Precondition can be simple or complex, complex precondition consists of multiple simple or complex preconditions as well.
Postcondition is something that is guaranteed to happen if preconditions are met & program behaves correctly.
Invariants is something that is guaranteed to hold, at least in observable moments in time, or perhaps even all the time.
If class user provides 'correct' / or using alternative wording: 'legal' / preconditions to object, methods will ensure that postconditions are met.
Invariants are always met / though some disagree, for there's 'observable moment' argument /, or contract is broken.
Examples for Preconditions:
- requirements for method arguments allowed values,
- concurrency requirements,
- perhaps more.
Examples for Postconditions:
- program's process(-es) will compute and provide results correctly,
- program will finish within the agreed time frame in at least 90% of situations,
- perhaps more.
Examples for Invariants:
- heat in Reactor will never go above the Critical Value,
- variable 'divisor' will never have '0' value,
- variable 'divisor' will never have '0' value during computations phase,
- perhaps more.
Inheritance / in simple words /.
To not break contract, following conditions must be met:
1. subclasses must require no more than it's neccessary for superclass to work correctly / but can require less /.
2. subclasses must meet all requirements of superclass / but perhaps can give more /.
This is related with the Liskov's Substitution Principle / LSP /.
Exceptions in Java.
When contract is broken during Runtime, an Exception should be thrown.
Design by Contract is the Software Collaboration Method.
Contract / between class user and class author / should state under which condition class will provide it's services to class user, and what these services are.
Contract.
There are Preconditions, Postconditions and Invariants that regulate contract.
Precondition is a condition that is required for something to happen. Precondition can be simple or complex, complex precondition consists of multiple simple or complex preconditions as well.
Postcondition is something that is guaranteed to happen if preconditions are met & program behaves correctly.
Invariants is something that is guaranteed to hold, at least in observable moments in time, or perhaps even all the time.
If class user provides 'correct' / or using alternative wording: 'legal' / preconditions to object, methods will ensure that postconditions are met.
Invariants are always met / though some disagree, for there's 'observable moment' argument /, or contract is broken.
Examples for Preconditions:
- requirements for method arguments allowed values,
- concurrency requirements,
- perhaps more.
Examples for Postconditions:
- program's process(-es) will compute and provide results correctly,
- program will finish within the agreed time frame in at least 90% of situations,
- perhaps more.
Examples for Invariants:
- heat in Reactor will never go above the Critical Value,
- variable 'divisor' will never have '0' value,
- variable 'divisor' will never have '0' value during computations phase,
- perhaps more.
Inheritance / in simple words /.
To not break contract, following conditions must be met:
1. subclasses must require no more than it's neccessary for superclass to work correctly / but can require less /.
2. subclasses must meet all requirements of superclass / but perhaps can give more /.
This is related with the Liskov's Substitution Principle / LSP /.
Exceptions in Java.
When contract is broken during Runtime, an Exception should be thrown.
Friday, 20 January 2023
A few thoughts on code quality - mostly for Java, but can be abstracted and used with different technologies.
In my opinion java code of quality should have following properties:
1. Proper naming of classess, methods, variables and constants.
2. Single, properly defined and documented responsibility of each class and method. No unneccessary code (to remove code duplication you can use constants (final keyword, UPPERCASE_NAMES) and split methods with large chunks of code into few smaller methods so you can reuse them. To ensure single responsibility of method or class move some code into another method or class. Single responsibility class or method is more reausable and easier to document, read, test and modify. [or to break if someone wants to try firing quality coder].). Single responsibility of method may involve calling more than one instruction as long as it is considered atomic. For example: changeStateWithSideEffect(...);
3. Documented methods headers (first lines of methods and all information therein, including variable names) according to javadoc documentation.
4. Use of 'assert' keyword, software contracts, preconditions, postconditions and invariants.
5. Fitting 'a complete code part' on a 'single screen', if possible and worthwhile; ... easier thinking, less scrolling, perhaps more.
Later JUnit/Easymock automated tests can be added to build test harness.
Also, code should be properly formatted.
Commits / to code repository, using technologies such as SVN or Git / should be commented.
Methods should be abstract, empty or final.
Ideally, methods should consists of three instructions. init(...); transform(...); return [(...)]; Complex instruction counts as single instruction;
There can be more requirements / for example: coding in idiomatic way / , but in practice it's almost perfect if these are used. Professionals after all have no time to comment code, or they want to be priceless and unfirable by bosses, in a not-so-nice, unfair way.
See also:
> [ Design by Contract ],
> [ 'SOLID': Five Principles for Object-Oriented Software Quality ],
> [ Software Development & Quality ].
1. Proper naming of classess, methods, variables and constants.
2. Single, properly defined and documented responsibility of each class and method. No unneccessary code (to remove code duplication you can use constants (final keyword, UPPERCASE_NAMES) and split methods with large chunks of code into few smaller methods so you can reuse them. To ensure single responsibility of method or class move some code into another method or class. Single responsibility class or method is more reausable and easier to document, read, test and modify. [or to break if someone wants to try firing quality coder].). Single responsibility of method may involve calling more than one instruction as long as it is considered atomic. For example: changeStateWithSideEffect(...);
3. Documented methods headers (first lines of methods and all information therein, including variable names) according to javadoc documentation.
4. Use of 'assert' keyword, software contracts, preconditions, postconditions and invariants.
5. Fitting 'a complete code part' on a 'single screen', if possible and worthwhile; ... easier thinking, less scrolling, perhaps more.
Later JUnit/Easymock automated tests can be added to build test harness.
Also, code should be properly formatted.
Commits / to code repository, using technologies such as SVN or Git / should be commented.
Methods should be abstract, empty or final.
Ideally, methods should consists of three instructions. init(...); transform(...); return [(...)]; Complex instruction counts as single instruction;
There can be more requirements / for example: coding in idiomatic way / , but in practice it's almost perfect if these are used. Professionals after all have no time to comment code, or they want to be priceless and unfirable by bosses, in a not-so-nice, unfair way.
See also:
> [ Design by Contract ],
> [ 'SOLID': Five Principles for Object-Oriented Software Quality ],
> [ Software Development & Quality ].
Thursday, 27 August 2020
'Three Spies Problem'.
By node in this post we understand internet device, network of such form a graph.
Communication from node A to node B can go through other transitory node T or through
transitory nodes T1, T2, ... Tn.
Then we can reach node B with message with 100% success rate if transitory node(s) won't fail.
We can send messages via transitory nodes in many ways.
Let's assume we have three transitory nodes, that is - T1, T2 and T3.
Then we can transmit a message:
1. Via random or predetermined node.
If that node fails, signal needs to be retransmitted.
2. Via all nodes at once, whole message.
It succeeds as long as at least one transitory node does not fail, but signal can be captured easier.
3. Via all nodes, 1/3 of message through each.
Transmission fails if at least 1 node fails. But lost part(s) of message can be resent later. There's less risk of capturing whole signal by opposing forces as well.
4. Via all nodes, 2/3 of message through each. (different 2/3 via each).
Transmission succeeds 100% of time when at least two nodes won't fail. Whole signal is captured if 2 transitory nodes are captured. When one node won't fail, 2/3 of signal are sent, then rest can be transmitted again.
When splitting signal into 2/3, whole has to be encrypted, then split into 3 parts, concatenated (joined) appropriately, then ecrypted each 2/3 again. It's difficult to decrypt message or its parts that way if one has no private keys.
For security, transmission can occur via different nodes (different internet route paths for example), and not at the same time. This can be done via three different internet cafes for example.
See also, if You wish, ... :
- 'Incoming Cipher Crisis'.
Communication from node A to node B can go through other transitory node T or through
transitory nodes T1, T2, ... Tn.
Then we can reach node B with message with 100% success rate if transitory node(s) won't fail.
We can send messages via transitory nodes in many ways.
Let's assume we have three transitory nodes, that is - T1, T2 and T3.
Then we can transmit a message:
1. Via random or predetermined node.
If that node fails, signal needs to be retransmitted.
2. Via all nodes at once, whole message.
It succeeds as long as at least one transitory node does not fail, but signal can be captured easier.
3. Via all nodes, 1/3 of message through each.
Transmission fails if at least 1 node fails. But lost part(s) of message can be resent later. There's less risk of capturing whole signal by opposing forces as well.
4. Via all nodes, 2/3 of message through each. (different 2/3 via each).
Transmission succeeds 100% of time when at least two nodes won't fail. Whole signal is captured if 2 transitory nodes are captured. When one node won't fail, 2/3 of signal are sent, then rest can be transmitted again.
When splitting signal into 2/3, whole has to be encrypted, then split into 3 parts, concatenated (joined) appropriately, then ecrypted each 2/3 again. It's difficult to decrypt message or its parts that way if one has no private keys.
For security, transmission can occur via different nodes (different internet route paths for example), and not at the same time. This can be done via three different internet cafes for example.
See also, if You wish, ... :
- 'Incoming Cipher Crisis'.
Sunday, 23 August 2020
Object State & Context.
About.
State / pl: 'stan' / can be defined in many ways.
Finite State Machine.
A finite-state machine (FSM) / pl: 'automat skończenie stanowy' / is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time.
The FSM can change from one state to another in response to some input.
States can be represented using circles; the change from one state to another is called a transition / pl: 'przejście', 'funkcja przejścia' / and can be represented on image using an arrow that points from one circle to the same or another circle, and is associated with input(s) that triggers a given transition.
An FSM is defined by:
- a list of its states,
- initial state / pl: 'stan początkowy' /,
- optionally acceptance (final) state(s) / pl: 'stan(y) akceptujący(-e)', 'stan(y) końcowy(-e)' /,
- transitions,
- inputs that trigger appropriate transitions.
Initial state can be represented by colouring nodes, for example - we can have black circles for non-initial states and green circle for initia state.
... for more, feel free to look: [ Finite-state machine on Wikipedia ].
Finite State Object.
One can look at object, at it's variables. Variables can be - and are - represented as list of 0's and 1's. Variable values can be concatenated into one list. All of possible permutations of 0's and 1's in this list represent all of possible of this object's states. State's name (label) can be a binary number, a list of 0's and 1's that changes when state changes. In this case we consider variables not by their's names, but by positions of their the values on the concatenated
state-bit-list.
Or, we can look at a state as on a combination of variable values, when we assign a list of 0's and 1's to each of variable names.
In both cases, object's type is important part of object's state, like a variable with it's value, represented by 0's and 1's, as any of information can be.
For details of the differencies between permutations and combinations, feel free to: click.
Similarly, object's methods can be seen as 'families' of transition functions / pl: 'rodziny funkcji przejścia' / between object's possible states. Object, method's name & possible parameter(s) - if any - passed to the method, together determine unambiguously / pl: 'jednoznacznie' / which transition to trigger.
In this way, object can be seen as finite state automaton, also called FSM - Finite State Machine.
... i call FSM implemented as object an FSO - Finite State Object.
In FSO, each of possible states can be represented graphically as a dot labelled with its list of 0's and 1's ... and method(s) - if any - is/are arrow(s) leading from one state to one or more other state(s). Obviously not every state must be connected with every other possible state. Not every method must change object's state as well ... then there's either no arrow associated with this method, or there is/are arrow(s) that point(s) to the same FSO that it originated from - useful when we want certain 'side effect(s)' to happen as a part of transition (see below).
FSO can have the 'side effects' that can trigger / pl: 'wyzwalać' / on transition, can send message(s) to other FSO(s), can call method(s) on other FSO(s). That way, Directed Graphs of FSOs can be seen as complete models of programs, that can be executed as well.
Context.
We can select a group of objects and contain it in another object, then states of contained objects are parts of grouping object's state. Anything outside connected to grouping object can be named 'context' / pl: kontekst /.
Speaking more abstractly and precisely, context is 'external state', is combined state of what surrounds the object, what is within certain distance from the considered object (we include objects' identities as a part of combined state here).
... and distance can be measured in many ways - not only in meters in straight line on map. It can be, for example, number of bus stops on the way to target. Or average time to reach 'Point B' from 'Point A'. Or number of nodes passed in graph, with weighted or unweighted edges.
Mind States.
I think and feel that buddhism's concept of Mind can be explained as similar to Finite State Machine(s).
For more details, feel free to look: [ Self-Improvement and Mind States ].
Links.
- Automata, Languages & Computations / Work in Progress Still /.
State / pl: 'stan' / can be defined in many ways.
Finite State Machine.
A finite-state machine (FSM) / pl: 'automat skończenie stanowy' / is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time.
The FSM can change from one state to another in response to some input.
States can be represented using circles; the change from one state to another is called a transition / pl: 'przejście', 'funkcja przejścia' / and can be represented on image using an arrow that points from one circle to the same or another circle, and is associated with input(s) that triggers a given transition.
An FSM is defined by:
- a list of its states,
- initial state / pl: 'stan początkowy' /,
- optionally acceptance (final) state(s) / pl: 'stan(y) akceptujący(-e)', 'stan(y) końcowy(-e)' /,
- transitions,
- inputs that trigger appropriate transitions.
Initial state can be represented by colouring nodes, for example - we can have black circles for non-initial states and green circle for initia state.
... for more, feel free to look: [ Finite-state machine on Wikipedia ].
Finite State Object.
One can look at object, at it's variables. Variables can be - and are - represented as list of 0's and 1's. Variable values can be concatenated into one list. All of possible permutations of 0's and 1's in this list represent all of possible of this object's states. State's name (label) can be a binary number, a list of 0's and 1's that changes when state changes. In this case we consider variables not by their's names, but by positions of their the values on the concatenated
state-bit-list.
Or, we can look at a state as on a combination of variable values, when we assign a list of 0's and 1's to each of variable names.
In both cases, object's type is important part of object's state, like a variable with it's value, represented by 0's and 1's, as any of information can be.
For details of the differencies between permutations and combinations, feel free to: click.
Similarly, object's methods can be seen as 'families' of transition functions / pl: 'rodziny funkcji przejścia' / between object's possible states. Object, method's name & possible parameter(s) - if any - passed to the method, together determine unambiguously / pl: 'jednoznacznie' / which transition to trigger.
In this way, object can be seen as finite state automaton, also called FSM - Finite State Machine.
... i call FSM implemented as object an FSO - Finite State Object.
In FSO, each of possible states can be represented graphically as a dot labelled with its list of 0's and 1's ... and method(s) - if any - is/are arrow(s) leading from one state to one or more other state(s). Obviously not every state must be connected with every other possible state. Not every method must change object's state as well ... then there's either no arrow associated with this method, or there is/are arrow(s) that point(s) to the same FSO that it originated from - useful when we want certain 'side effect(s)' to happen as a part of transition (see below).
FSO can have the 'side effects' that can trigger / pl: 'wyzwalać' / on transition, can send message(s) to other FSO(s), can call method(s) on other FSO(s). That way, Directed Graphs of FSOs can be seen as complete models of programs, that can be executed as well.
Context.
We can select a group of objects and contain it in another object, then states of contained objects are parts of grouping object's state. Anything outside connected to grouping object can be named 'context' / pl: kontekst /.
Speaking more abstractly and precisely, context is 'external state', is combined state of what surrounds the object, what is within certain distance from the considered object (we include objects' identities as a part of combined state here).
... and distance can be measured in many ways - not only in meters in straight line on map. It can be, for example, number of bus stops on the way to target. Or average time to reach 'Point B' from 'Point A'. Or number of nodes passed in graph, with weighted or unweighted edges.
Mind States.
I think and feel that buddhism's concept of Mind can be explained as similar to Finite State Machine(s).
For more details, feel free to look: [ Self-Improvement and Mind States ].
Links.
- Automata, Languages & Computations / Work in Progress Still /.
Wednesday, 1 April 2020
Tuple Data Type.
Nice Notation.
Must admit that i love these parts of Computer Sciences that have elegant, scientific notation.
Tuples / pl: 'Krotki' / are nice that way, as well.
For example:
(char, int8, int8, string) t1 := ('a', 1, 3, "sample string");
(int8, int8) t2 := (2,3);
Uses.
Was thinking about how to implement Tuple Data Type in 'Ola' Programming Language.
Preconditions.
i think that every object used with 'Ola' Programming Language ... should have a 'name' string as a part of its runtime state, randomly generated at first, with Random Number Generator initialized with a Time Stamp.
i think it should be possible to rename any/every of object(s).
Succesful working of the Tuple Data Type depends on above preconditions. Without these preconditions, this article should be either edited or removed.
Implementation Considerations.
Was thinking about how to implement Tuple Data Type in 'Ola' Programming Language - and came with that a tuple - internally - should consist of:
- String Array with runtime object names,
- Map where object name string is key and TupleValue is value.
Invariant: During Map's observable moments, name strings in Map are sorted alphabetically.
TupleValue has:
- object's type / not sure yet how to encode it /,
- object's value / according with it's type /.
Benefits.
1. Using String Array and Map, we provide support for objects graph that can contain cycles.
Names in objects' runtime state are also important tool for avoiding 'infinite recursion' loops in graphs with cycles.
2. Thanks to String Array and Map data types used, it's cheap and easy to find n-th value in a tuple ... both n-th key, as well as n-th TupleValue.
/ Algorithmic time: Worst: O(1) for retrieving key, and Worst: O(1) for retrieving value /
For example:
(int8, int8, int8) t := (1,5,3);
String tk := t.getKey(2);
TupleValue tv := t.getValue(2);
3. We can also quickly get String Array part of a Tuple ... in which an unsorted copy of keyset is kept.
/ Algorithmic time: Worst: O(1) /
For example:
(int32, int8, int8, int8) t := (15,6,5,3);
String[] keys := t.getKeys();
4. Giving a name to a tuple value is also cheap and easy,
/ Algorithmic time: Worst: O(1) /
For example:
(int8, int8, int8) t := (2,4,3);
t.setName(2, "name for 3");
// both String Array, as well as Map's key are updated ... both need to be a part of a single atomic operation.
5. Searching for a tuple value by its name is also easy and cheap.
/ Algorithmic time of insertion/lookup in Java's LinkedHashMap is: Amortized Worst: O(1) /
For example:
(char, int8, string, int8) t := ('2',4,"one",0);
t.setName(2, "name for one");
TupleValue tv := t.getTupleValueByName("name for one");
Links.
- Linda & Tuple Space,
- Algorithms' Time-Performance Metrics.
Must admit that i love these parts of Computer Sciences that have elegant, scientific notation.
Tuples / pl: 'Krotki' / are nice that way, as well.
For example:
(char, int8, int8, string) t1 := ('a', 1, 3, "sample string");
(int8, int8) t2 := (2,3);
Uses.
Was thinking about how to implement Tuple Data Type in 'Ola' Programming Language.
Preconditions.
i think that every object used with 'Ola' Programming Language ... should have a 'name' string as a part of its runtime state, randomly generated at first, with Random Number Generator initialized with a Time Stamp.
i think it should be possible to rename any/every of object(s).
Succesful working of the Tuple Data Type depends on above preconditions. Without these preconditions, this article should be either edited or removed.
Implementation Considerations.
Was thinking about how to implement Tuple Data Type in 'Ola' Programming Language - and came with that a tuple - internally - should consist of:
- String Array with runtime object names,
- Map where object name string is key and TupleValue is value.
Invariant: During Map's observable moments, name strings in Map are sorted alphabetically.
TupleValue has:
- object's type / not sure yet how to encode it /,
- object's value / according with it's type /.
Benefits.
1. Using String Array and Map, we provide support for objects graph that can contain cycles.
Names in objects' runtime state are also important tool for avoiding 'infinite recursion' loops in graphs with cycles.
2. Thanks to String Array and Map data types used, it's cheap and easy to find n-th value in a tuple ... both n-th key, as well as n-th TupleValue.
For example:
(int8, int8, int8) t := (1,5,3);
String tk := t.getKey(2);
TupleValue tv := t.getValue(2);
3. We can also quickly get String Array part of a Tuple ... in which an unsorted copy of keyset is kept.
For example:
(int32, int8, int8, int8) t := (15,6,5,3);
String[] keys := t.getKeys();
4. Giving a name to a tuple value is also cheap and easy,
(int8, int8, int8) t := (2,4,3);
t.setName(2, "name for 3");
// both String Array, as well as Map's key are updated ... both need to be a part of a single atomic operation.
5. Searching for a tuple value by its name is also easy and cheap.
(char, int8, string, int8) t := ('2',4,"one",0);
t.setName(2, "name for one");
TupleValue tv := t.getTupleValueByName("name for one");
Links.
- Linda & Tuple Space,
- Algorithms' Time-Performance Metrics.
Thursday, 19 March 2020
Algorithms' Time-Performance Metrics.
What is Algorithm?
An algorithm is a procedure or formula for solving a problem, based on conducting a sequence of specified actions.
Algorithms + Data Structures = Programs.
The more we know about input data, the better-fitting algorithms we can choose - which may significiantly improve program's performance.
Computational Complexity.
Algorithm's Computational Complexity is defined as amount of computer's resources needed for given algorithm's execution.
The most basic such resources are:
- Processor Time,
- Amount of Memory.
Let's notice that usually it's not possible to form computational complexity as function of input data / such as: strings, arrays, trees or graphs /.
Usually what we have is only data size, understood as amount of input data.
For example:
- In a sorting problem - as data size we consider amount of elements in an input string,
- In a binary tree traversal problem, as data size we consider amount of nodes in a tree,
To be able to define Computational Complexity of Algorithm, we must agree on units in which it's measured.
Computational Complexity consists of:
- Time Complexity,
- Memory Complexity.
Time Complexity should depend on Algorithm itself, should be independent of computer, programming language, or details of coding it's realized with.
For this, we select certain operations characteristic to such algorithm - we'll call these: 'Dominant Operations'. Dominant Operations must have also following quality: amount of Dominant Operations executions is proportional to the total amount of operations executed by any of computer program's realizations.
For sorting algorithms, as dominant operation we usually choose comparison operation in an input data string, but occasionally also operation that swaps places of two pieces in input string data.
As unit of time complexity we define an execution of one dominant operation.
Computational Complexity of Algorithm we treat as a function of data size n.
We can consider:
- Pessimistic Algorithm's Complexity - defined as amount of resources needed for 'worst case' of input data,
- Expected Algorithm's Complexity - defined as amount of resources needed for 'typical case' of input data.
Definitions.
To define concepts of pesimistic and expected time complexity function, we'll use following symbols:
Dn - a set of input data sets, each of size n;
t(d) - amount of dominant operations for a input data set d;
Xn - random variable - it's value is t(d) for d ∊ Dn;
pnk - probability distribution of a random variable Xn, probability that for data size n algorithm will execute k of dominant operations (k ≥ 0).
Algorithm's pessimistic time complexity, we understand as function:
W(n) = sup { t(d): d ∊ Dn },
Where: 'sup' means: 'upper limit of the set'.
Algorithm's expected time complexity, we understand as function:
Meaning: expected value ave(Xn) of random variable Xn.
Notation for Bounds.
Big O (O()) describes the upper bound of the complexity.
Omega (Ω()) describes the lower bound of the complexity.
Theta (Θ()) describes the 'exact' bound of the complexity, between O() and Ω().
Little O (o()) describes the upper bound excluding the exact bound.
For example, let's consider Hoare's QuickSort Algorithm, Randomized version*:
QuickSort's expected complexity is linear - logarithmic: Θ(n•log n),
QuickSort's worst case complexity is square: O(n2).
* Scientific proofs for given algorithm's complexity values can be found in 'Introduction to Algorithms' book by:
- Thomas H. Cormen,
- Carles E. Leiserson,
- Ronald L. Rivest.
See also if You wish:
- What is Big O Notation Explained: Space and Time Complexity|.
Running Time.
Actual time complexity of an Algorithm / its running time / when used as a program, differs theoretically by proportionality factor that depends on used realization of this given algorithm.
Therefore, important part of information in complexity functions W(n) and A(n) is their order of magnitude - asymptotic behavior when n tends to infinity.
The most often we try to give simplest possible function that characterizes order of magnitude W(n) and A(n), for example: n, n•log n, n2, n3.
Typical Proportions.
The most of considered algorithms have time complexity that is proportional to one of functions:
1. log(n) - logarithmic complexity / pl: złożoność logarytmiczna /.
Logarithmic time complexity occurs - for example - with algorithms of type:
Exercise of size n is reduced to task of size n/2 + a certain amount of constant operations.
For example: binary search in a sorted input data set: a1 ≤ a2 ≤ ... ≤ an.
2. n - linear complexity / pl: złożoność liniowa /.
Linear time complexity occurs - for example - with algorithms in which we execute constant amount of operations for each of n elements in input data.
Example of such algorithm is Horner's Algorithm for determining polynomial's values.
3. n•log(n) - linear-logarithmic complexity / pl: złożoność liniowo - logarytmiczna /.
4. n2 - square complexity / pl: złożoność kwadratowa /.
5. n3, n4 - polynomial complexity / pl: złożoność wielomianowa /.
6. 2n - exponential complexity 2n / pl: złożoność wykładnicza 2n /.
7. n! - exponential complexity n! / pl: złożoność wykładnicza n! /.
Time-Consuming Algorithms.
Let's notice that algorithms with exponential complexity can solve its problems only for a small amount of input data size.
There's treshold, starting from which exponential function starts to increase its value so fast, that realizing algorithm on a computer becomes impossible.
As for example, let's assume that we have:
- input data set, its size is n,
- algorithm with time complexity 2n,
- two computers:
- on first computer, the dominant operation executes in 10-6 second,
- on second computer, the dominant operation executes in 10-9 second.
Time needed to perform calculations by our algorithm is presented in a following table:
That is, for time-consuming exponential algorithms - using even 1000 times faster computers might mean almost nothing in practice.
It doesn't matter much that precise time differs on different computers, with different software and hardware.
This is only an example, presented here to convey idea of how important Algorithmic Speed is.
An algorithm is a procedure or formula for solving a problem, based on conducting a sequence of specified actions.
Algorithms + Data Structures = Programs.
The more we know about input data, the better-fitting algorithms we can choose - which may significiantly improve program's performance.
Computational Complexity.
Algorithm's Computational Complexity is defined as amount of computer's resources needed for given algorithm's execution.
The most basic such resources are:
- Processor Time,
- Amount of Memory.
Let's notice that usually it's not possible to form computational complexity as function of input data / such as: strings, arrays, trees or graphs /.
Usually what we have is only data size, understood as amount of input data.
For example:
- In a sorting problem - as data size we consider amount of elements in an input string,
- In a binary tree traversal problem, as data size we consider amount of nodes in a tree,
To be able to define Computational Complexity of Algorithm, we must agree on units in which it's measured.
Computational Complexity consists of:
- Time Complexity,
- Memory Complexity.
Time Complexity should depend on Algorithm itself, should be independent of computer, programming language, or details of coding it's realized with.
For this, we select certain operations characteristic to such algorithm - we'll call these: 'Dominant Operations'. Dominant Operations must have also following quality: amount of Dominant Operations executions is proportional to the total amount of operations executed by any of computer program's realizations.
For sorting algorithms, as dominant operation we usually choose comparison operation in an input data string, but occasionally also operation that swaps places of two pieces in input string data.
As unit of time complexity we define an execution of one dominant operation.
Computational Complexity of Algorithm we treat as a function of data size n.
We can consider:
- Pessimistic Algorithm's Complexity - defined as amount of resources needed for 'worst case' of input data,
- Expected Algorithm's Complexity - defined as amount of resources needed for 'typical case' of input data.
Definitions.
To define concepts of pesimistic and expected time complexity function, we'll use following symbols:
Dn - a set of input data sets, each of size n;
t(d) - amount of dominant operations for a input data set d;
Xn - random variable - it's value is t(d) for d ∊ Dn;
pnk - probability distribution of a random variable Xn, probability that for data size n algorithm will execute k of dominant operations (k ≥ 0).
Algorithm's pessimistic time complexity, we understand as function:
Algorithm's expected time complexity, we understand as function:
Notation for Bounds.
Big O (O()) describes the upper bound of the complexity.
Omega (Ω()) describes the lower bound of the complexity.
Theta (Θ()) describes the 'exact' bound of the complexity, between O() and Ω().
Little O (o()) describes the upper bound excluding the exact bound.
For example, let's consider Hoare's QuickSort Algorithm, Randomized version*:
QuickSort's expected complexity is linear - logarithmic: Θ(n•log n),
QuickSort's worst case complexity is square: O(n2).
* Scientific proofs for given algorithm's complexity values can be found in 'Introduction to Algorithms' book by:
- Thomas H. Cormen,
- Carles E. Leiserson,
- Ronald L. Rivest.
See also if You wish:
- What is Big O Notation Explained: Space and Time Complexity|.
Running Time.
Actual time complexity of an Algorithm / its running time / when used as a program, differs theoretically by proportionality factor that depends on used realization of this given algorithm.
Therefore, important part of information in complexity functions W(n) and A(n) is their order of magnitude - asymptotic behavior when n tends to infinity.
The most often we try to give simplest possible function that characterizes order of magnitude W(n) and A(n), for example: n, n•log n, n2, n3.
Typical Proportions.
The most of considered algorithms have time complexity that is proportional to one of functions:
1. log(n) - logarithmic complexity / pl: złożoność logarytmiczna /.
Logarithmic time complexity occurs - for example - with algorithms of type:
Exercise of size n is reduced to task of size n/2 + a certain amount of constant operations.
For example: binary search in a sorted input data set: a1 ≤ a2 ≤ ... ≤ an.
2. n - linear complexity / pl: złożoność liniowa /.
Linear time complexity occurs - for example - with algorithms in which we execute constant amount of operations for each of n elements in input data.
Example of such algorithm is Horner's Algorithm for determining polynomial's values.
3. n•log(n) - linear-logarithmic complexity / pl: złożoność liniowo - logarytmiczna /.
4. n2 - square complexity / pl: złożoność kwadratowa /.
5. n3, n4 - polynomial complexity / pl: złożoność wielomianowa /.
6. 2n - exponential complexity 2n / pl: złożoność wykładnicza 2n /.
7. n! - exponential complexity n! / pl: złożoność wykładnicza n! /.
Time-Consuming Algorithms.
Let's notice that algorithms with exponential complexity can solve its problems only for a small amount of input data size.
There's treshold, starting from which exponential function starts to increase its value so fast, that realizing algorithm on a computer becomes impossible.
As for example, let's assume that we have:
- input data set, its size is n,
- algorithm with time complexity 2n,
- two computers:
- on first computer, the dominant operation executes in 10-6 second,
- on second computer, the dominant operation executes in 10-9 second.
Time needed to perform calculations by our algorithm is presented in a following table:
| Size n | 20 | 50 | 100 | 200 |
| Calculation time (2n/106) | 1,04 s | 35,7 years | 4∙1014 ages | 5∙1044 ages |
| Calculation time (2n/109) | 0,001 s | 13 days | 4∙1011 ages | 5∙1041 ages |
That is, for time-consuming exponential algorithms - using even 1000 times faster computers might mean almost nothing in practice.
It doesn't matter much that precise time differs on different computers, with different software and hardware.
This is only an example, presented here to convey idea of how important Algorithmic Speed is.
Subscribe to:
Posts (Atom)